多面体グラフ

多面体グラフ（ためんたいグラフ）は凸多面体の頂点と辺からなる無向グラフであり、純粋なグラフ理論的には、多面体グラフは3-頂点連結グラフである平面グラフである。

特徴

凸多面体のシュレーゲル図は、凸多面体の頂点と辺をユークリッド平面上の点と辺として表現し、外側の凸多角形をより小さい凸多角形に細分する。辺は交差しないため、多面体グラフは平面グラフであり、バリンスキーの定理より、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.

特殊な例

多面体グラフが立方体グラフならば、その立方体グラフは、多面体の次元と各頂点の次数が一致する多面体（simple polytedron）のグラフである。多面体グラフが最大平面グラフ（辺を加えることで平面グラフではなくなるグラフ）ならば、多面体グラフが単体に対応する多面体グラフである。また、木のすべての葉を接続する閉路を外側に追加することによって生成されるHalinグラフは、多面体グラフの別の重要な概念となる。

注釈・出典

^ Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 0-387-94365-X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.
^ Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, 221 (2nd ed.), Springer-Verlag, ISBN 978-0-387-40409-7 .
^ Tutte, W. T. (1963), “How to draw a graph”, Proceedings of the London Mathematical Society 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR0158387 .
^ Weisstein, Eric W. "Herschel Graph". MathWorld.
^ Weisstein, Eric W. "Goldner-Harary Graph". MathWorld.
^ Weisstein, Eric W. "Shortness Exponent". MathWorld.
^ Grünbaum, Branko; Motzkin, T. S. (1962), “Longest simple paths in polyhedral graphs”, Journal of the London Mathematical Society s1-37 (1): 152–160, doi:10.1112/jlms/s1-37.1.152 .
^ Duijvestijn, A. J. W. (1996), “The number of polyhedral (3-connected planar) graphs”, Mathematics of Computation 65: 1289–1293, doi:10.1090/S0025-5718-96-00749-1 .

外部リンク

Weisstein, Eric W. "Polyhedral Graph". MathWorld.

[1] Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 0-387-94365-X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.

[grun-2] Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, 221 (2nd ed.), Springer-Verlag, ISBN 978-0-387-40409-7 .

[3] Tutte, W. T. (1963), “How to draw a graph”, Proceedings of the London Mathematical Society 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR0158387 .

[4] Weisstein, Eric W. "Herschel Graph". MathWorld.

[5] Weisstein, Eric W. "Goldner-Harary Graph". MathWorld.

[6] Weisstein, Eric W. "Shortness Exponent". MathWorld.

[7] Grünbaum, Branko; Motzkin, T. S. (1962), “Longest simple paths in polyhedral graphs”, Journal of the London Mathematical Society s1-37 (1): 152–160, doi:10.1112/jlms/s1-37.1.152 .

[8] Duijvestijn, A. J. W. (1996), “The number of polyhedral (3-connected planar) graphs”, Mathematics of Computation 65: 1289–1293, doi:10.1090/S0025-5718-96-00749-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]