多面体グラフ
From Wikipedia, the free encyclopedia
凸多面体のシュレーゲル図は、凸多面体の頂点と辺をユークリッド平面上の点と辺として表現し、外側の凸多角形をより小さい凸多角形に細分する。辺は交差しないため、多面体グラフは平面グラフであり、バリンスキーの定理より、3-頂点連結グラフである。
シュタイニッツの定理より、この2つのグラフ理論的性質「3-頂点連結グラフである」と「平面グラフである」は多面体グラフを完全に特徴づけるのに十分である。つまり、グラフが「3-頂点連結グラフであり」「平面グラフである」ならば、頂点と辺が同じようにつながる（＝グラフ同型な）多面体が存在する[1][2]。そのようなグラフが与えられれば、凸多角形をより小さな凸多角形に細分化したものを、Tutte embeddingを用いて表現できる[3]。
ハミルトン路の存在とその最短性
P. G. テイトは「3次の多面体グラフはハミルトン路を持つ」というテイト予想 (グラフ理論)を1884年に提唱したが、この予想1946年にはW. T. Tutteによってタットグラフと呼ばれるハミルトン路を持たない多面体グラフはにより反証された。更に、4次以下の多面体グラフと言う条件ならばより小さな11頂点・18辺からなるハーシェルグラフ[4]、4次以上の頂点を含むが、面が三角形のみである多面体グラフならば11頂点27辺からなるゴールドナー・ハラリーグラフがハミルトン路を持たないグラフとして知られている[5]。
より強い主張として、ある α < 1 （shortness exponent）に対し最長の道が無限個の多面体グラフが存在し、頂点数 n に対してO(nα)個ある[6][7]。
グラフ列挙
Duijvestijnは多面体グラフの種類を26辺からなるものまで数え上げた[8]。6、7、8、…本の辺からなる多面体グラフの数は、
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (sequence オンライン整数列大辞典の数列 A002840.
また、頂点数別に多面体グラフを数え上げると、4、5、6、…個の頂点からなる多面体グラフの数は、
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (sequence オンライン整数列大辞典の数列 A000944.