第３講 多面体のグラフ
多面体Pに関して一般の位置
面の向こう側
辺の向きづけ(Orientation of G(P) induced by )
頂点と辺とで構成されたものをグラフとするなら、多面体はn次元空間に表示されたグラフである。
凸多面体は、一般の位置にある任意のベクトル方向について、頂点集合が半順序になるような多面体とも言える。
多面体の頂点・辺を２次元空間に表したものは、通常の意味でのグラフ表現である。n次元空間に表示されたグラフとの違いは、２次元空間上グラフにしようとするとうまく描かないと、描図上、辺が交わるが、それらが交点を持たないことを「描図上の約束」として観察者が知っているのに対して、n次元空間表示のグラフは、辺の交わりがないことである。
この伝で行くと、１次元空間表示のグラフ(様)表示もあって、この場合は、辺の交わりを許しているだけではなくて、辺の完全なオーバーラップをも許している。もしも、観察者が見るだけで「知りうる」表示法があれば、凸多面体の１次元空間表現も可能となる。ここで、頂点集合の半順序は、この１次元空間表現での座標として与えることも可能である。さらにいえば、「優れた観察者」は０次元でも凸多面体の頂点の半順序関係を「知る」ことができるだろう。
ヒルシュ予想(凸多面体グラフの直径は、
を満たすとするもの。ただし
は頂点数、
は多面体の次元である。この予想は0/1-多面体では成立することが確かめられている。
バリンスキーの定理(d-多面体のグラフはd-連結である)
