多面体グラフ

多面体グラフの概要

多面体グラフは、凸多面体の頂点と辺から成る無向グラフです。このグラフは純粋にグラフ理論の観点から見ても重要であり、3-頂点連結グラフである平面グラフと位置づけられています。

特徴と構造

凸多面体のシュレーゲル図を用いることで、これらのグラフはユークリッド平面における点と辺として視覚的に表現することができます。この場合、外周を形成する凸多角形は、小さな凸多角形へと細分化されます。辺同士は交差せず、これは多面体グラフが平面グラフであることを示しています。バリンスキーの定理によれば、すべての多面体グラフは3-頂点連結であり、これはシュタイニッツの定理とも相まって、平面グラフであることが多面体グラフを定義づけるのに十分な条件です。したがって、もしグラフが「3-頂点連結グラフであり、なおかつ平面グラフである」場合、その接続構造は相互に同型な多面体として表現可能です。生じる多面体グラフが与えられれば、Tutte embedding技法によって凸多角形を小さな凸多角形に分割して表示できます。

ハミルトン路に関する考察

P. G. テイトが1884年に提唱した「3次の多面体グラフはハミルトン路を持つ」という主張は、「テイト予想」として知られていますが、1946年にW. T. Tutteによってこの予想は反証されました。その根拠となるのは、タットグラフと呼ばれる特定の多面体グラフがハミルトン路を持たないことが証明された点です。また、4次以下の多面体グラフの条件下でも、ハミルトン路を持たないグラフの具体例が存在します。これには、11頂点と18辺を有するハーシェルグラフや、面が三角形のみで構成される11頂点27辺のゴールドナー・ハラリーグラフなどが含まれます。

さらに、あるショートネス指数α（α < 1）を持つ最長路が無限個存在し、頂点数nに対しO(n^α)個の多面体グラフが存在することも示されています。

グラフの数え上げ

多面体グラフのバリエーションは多様であり、Duijvestijnによって26辺を持つ多面体グラフまでが数え上げられています。6、7、8...と幅を広げると、これまでの調査に基づいて得られた多面体グラフの数は、次のように表されています：

• - 6辺: 1
• - 7辺: 0
• - 8辺: 1
• - 9辺: 2
• - 10辺: 2
• - 11辺: 4
• - 12辺: 12
• - 13辺: 22
• - 14辺: 58
• - ...

また、4、5、6...と続く頂点数を基準にした場合、多面体グラフの数も明示的に数え上げられています。記録では次のようになっています：

• - 4頂点: 1
• - 5頂点: 2
• - 6頂点: 7
• - 7頂点: 34
• - 8頂点: 257
• - ...

特殊な多面体グラフの例

立方体グラフは特に興味深い例です。立方体の各頂点の次数がその次元に相当する形で、多面体の特性が反映されています。また、最大平面グラフの場合は、これが単体に関連する多面体として表現されます。さらに、Halinグラフは特定の方法で生成されることからも注目されています。これは、木の全ての葉を接続するループを外周に追加することで形成されます。

参考文献

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

もう一度検索