シュタイニッツの定理

数学の一分野である多面体組合せ論において、シュタイニッツの定理は、3次元の凸多面体の辺と頂点によって形成される無向グラフの特徴付けであり、それらはまさに3頂点連結平面グラフである。つまり、すべての凸多面体は3連結平面グラフを形成し、すべての3連結平面グラフは凸多面体のグラフとして表すことができる。このため、3連結平面グラフは多面体グラフとも呼ばれる。^[1]

この結果は、3次元凸多面体の分類定理を提供するもので、高次元では知られていないものである。 ^[2]この定理は、これらの多面体のグラフの完全かつ純粋な組み合わせ記述を提供し、これらの形状の幾何学を参照することなく、与えられた種類の面を持つ多面体の実現に関するエバーハルトの定理など、それらに関する他の結果をより簡単に証明することを可能にする。 ^[3]さらに、この定理は、抽象的なグラフの3次元視覚化を構築する方法として、グラフ描画に適用されている。 ^[4] ブランコ・グリュンバウムは、この定理を「 3次元多面体に関する最も重要で最も深い既知の結果」と呼んでいる。 ^[5]

この定理は、エルンスト・シュタイニッツ^[6]の1922年の出版物に掲載されており、彼の名にちなんで名付けられています。この定理は、数学的帰納法（シュタイニッツが行ったように）、2次元バネシステムの最小エネルギー状態を見つけてその結果を3次元に持ち上げること、または円充填定理を使用することによって証明できます。定理の拡張はいくつか知られており、与えられたグラフを実現する多面体に追加の制約があります。たとえば、すべての多面体グラフは、整数座標を持つ凸多面体のグラフ、またはすべての辺が共通の中心球に接する凸多面体のグラフです。

無向グラフは頂点と辺のシステムであり、各辺は頂点のうちの 2 つを接続します。グラフ理論では一般的ですが、スタインイッツの定理の目的上、これらのグラフは有限 (頂点と辺は有限集合) かつ単純 (2 つの辺が同じ 2 つの頂点を接続しておらず、辺が頂点自体を接続していない) に制限されます。任意の多面体からグラフを形成できます。グラフの頂点を多面体の頂点に対応させ、対応する 2 つの多面体頂点が多面体の辺の端点である場合はいつでも、任意の 2 つのグラフ頂点を辺で接続します。このグラフは多面体のスケルトンとして知られています。^[7]

グラフが平面的であるとは、その頂点をユークリッド平面上の点として、その辺をこれらの点を結ぶ曲線として描くことができ、2 つの辺曲線が互いに交差せず、頂点を表す点が辺を表す曲線上にあるのは、頂点が辺の端点である場合のみである。ファリーの定理により、すべての平面描画は、辺を表す曲線が線分になるように直線化できる。グラフが3 つ以上の頂点を持ち、その頂点のうちの 2 つを削除した後も、他の​​任意の 2 つの頂点がパスで接続されたままである場合、そのグラフは3 連結である。シュタイニッツの定理は、これらの 2 つの条件が 3 次元凸多面体の骨格を特徴付けるのに必要かつ十分であると述べている。与えられたグラフが凸 3 次元多面体のグラフであるためには、そのグラフが平面かつ 3 頂点連結である場合に限る。 ^{[5] [8]}${\displaystyle G}$${\displaystyle G}$

シュタイニッツの定理の 1 つの方向 (証明しやすい方向) は、すべての凸多面体のグラフは平面で 3 連結であると述べています。図に示すように、平面性はシュレーゲル図を使用して示すことができます。多面体の 1 つの面の近くに光源を配置し、反対側に平面を配置すると、多面体のエッジの影が平面グラフを形成し、エッジが直線セグメントになるように埋め込まれます。多面体グラフの 3 連結性は、任意の-次元凸多面体のグラフは- 連結であるというバリンスキーの定理の特殊なケースです。多面体のグラフの接続性は、頂点を削除した後、もう1つの頂点を選択し、その結果得られた頂点の集合上でゼロになる線形関数を見つけ、単体法によって生成されたパスをたどってすべての頂点を線形関数の2つの端点のいずれかに接続し、選択した頂点が両方に接続されることによって証明できます。^[9]${\displaystyle k}$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle v}$${\displaystyle k}$${\displaystyle v}$

シュタイニッツの定理のもう 1 つの、より難しい方向は、すべての平面 3 連結グラフは凸多面体のグラフである、というものです。この部分には、帰納法による証明、マクスウェル-クレモナ対応を使用して 2 次元のTutte 埋め込みを3 次元に持ち上げる方法、円充填定理を使用して標準多面体を生成する方法という3 つの標準的なアプローチがあります。

シュタイニッツの元の証明はグラフ理論で表現されていなかったが、グラフ理論で書き直すことができ、任意の 3 連結平面グラフを四面体のグラフ に縮小するΔY 変換と YΔ 変換のシーケンスを見つけることを含む。YΔ 変換は、グラフから次数 3 の頂点を削除し、それらのエッジがまだ存在していなかった場合は、以前のすべての隣接頂点間にエッジを追加する。逆の変換である ΔY 変換は、グラフから三角形のエッジを削除し、同じ 3 つの頂点に隣接する新しい次数 3 の頂点でそれらを置き換える。このようなシーケンスが見つかったら、それを逆にして、四面体から始めて段階的に目的の多面体を構築する幾何学的操作に変換することができる。逆シーケンスの各 YΔ 変換は、多面体から次数 3 の頂点を切り取ることによって幾何学的に実行できる。逆順の ΔY 変換は、多面体から三角形の面を削除し、隣接する面をそれらが出会う点まで延長することによって幾何学的に実行できますが、3 つの隣接する面の三重交差点が多面体から削除された面の反対側にある場合のみです。三重交差点がこの面の反対側にない場合は、多面体の射影変換で正しい側に移動できます。したがって、与えられたグラフを に縮小するために必要な ΔY 変換と YΔ 変換の数を帰納的に計算すると、すべての多面体グラフを多面体として実現できます。^[5]${\displaystyle K_{4}}$${\displaystyle K_{4}}$

エピファノフによるその後の研究は、あらゆる多面体グラフはΔY 変換と YΔ 変換によって に簡約できるという Steinitz の証明を強化した。エピファノフは、平面グラフで 2 つの頂点が指定されている場合、 ΔY 変換と YΔ 変換を直列並列簡約と組み合わせることで、グラフをそれらの端子間の単一の辺に簡約できることを証明した。^[10]エピファノフの証明は複雑で非構成的であったが、トゥルーエンパーがグラフマイナーに基づく方法を使用して簡略化した。トゥルーエンパーは、あらゆるグリッドグラフはこのように ΔY 変換と YΔ 変換によって簡約可能であり、この簡約可能性はグラフマイナーによって保持され、あらゆる平面グラフはグリッドグラフのマイナーであることを観察した。^[11]このアイデアは、簡約シーケンスが存在するという Steinitz の補題を置き換えるために使用できる。この置き換えの後、残りの証明は Steinitz の元の証明と同じように帰納法を使用して実行できる。^[8]これらの証明は、ΔY変換とYΔ変換のシーケンスを見つける方法のいずれかを使用して実行され、非線形数のステップを必要とする多面体グラフが存在します。より正確には、すべての平面グラフは最大で に比例するステップ数を使用して縮小でき、無限に多くのグラフは少なくとも に比例するステップ数を必要とします。ここで はグラフの頂点の数です。^{[12] [13]}${\displaystyle K_{4}}$${\displaystyle n^{3/2}}$${\displaystyle n^{3/2}}$${\displaystyle n}$

帰納的証明の別の形式は、辺の削除（および削除後に残る可能性のある次数 2 の頂点の圧縮）または辺の縮小と与えられた平面グラフのマイナーの形成に基づいています。任意の多面体グラフは、これらの操作の線形回数で に縮小でき、また操作を逆にして、その操作を幾何学的に実行することで、グラフの多面体実現が得られます。ただし、このタイプの議論では縮小シーケンスが存在することを証明する方が簡単で、縮小シーケンスは短くなりますが、シーケンスを逆にするために必要な幾何学的手順はより複雑になります。^[14]${\displaystyle K_{4}}$

グラフが直線のエッジを持つ平面に描かれている場合、平衡応力は、各頂点が隣接する頂点の加重平均によって与えられた位置にあるという特性を持つ、エッジへの非ゼロの実数 (重み) の割り当てとして定義されます。マクスウェル - クレモナ対応によれば、平衡応力は、表面の平坦な部分の間の境界を形成するエッジが与えられた描画に投影されるように、区分線形の連続した 3 次元表面に持ち上げることができます。各エッジの重みと長さによって、エッジの両側の表面の傾斜の差が決まり、各頂点が隣接する頂点と平衡状態にあるという条件は、これらの傾斜の差によって表面が頂点の近傍で正しく一致するという条件と同等です。正の重みは区分線形表面の 2 つの面の間の凸状の二面角に変換され、負の重みは凹状の二面角に変換されます。逆に、すべての連続した区分線形表面は、このように平衡応力から生じます。有限平面グラフを描き、そのグラフのすべての内側の辺に正の重みが与えられ、すべての外側の辺に負の重みが与えられるような平衡応力を与えられた場合、この応力をこのように3次元表面に変換し、グラフの外側を表す平面を同じ平面内の補平面に置き換えると、凸多面体が得られ、その平面への垂直投影には交差がないという追加の特性を持つ。^{[15] [16]}

マクスウェル・クレモナ対応は、WT タットの平面グラフ描画法であるタット埋め込みと組み合わせることで、多面体グラフの多面体実現を得るために使用されてきた。タットの方法は、多面体グラフの 1 つの面を平面内の凸位置に固定することから始まる。この面は、グラフの描画の外側の面になる。この方法は、頂点座標で線形方程式系を設定し、それに従って残りの各頂点をその近傍の平均に配置することによって続行される。すると、タットが示したように、この方程式系は、グラフの各面が凸多角形として描画される唯一の解を持つことになる。^[17]直感的には、この解は、グラフの内側のエッジを理想的なバネに置き換え、それらを最小エネルギー状態に落ち着かせることによって得られるパターンを記述する。^[18]結果はほぼ平衡応力であり、各内側のエッジに重み 1 を割り当てると、描画の各内側の頂点は平衡状態になる。しかし、外辺に負の数を割り当てて、それらも平衡状態になるようにすることは常に可能というわけではない。そのような割り当ては、外面が三角形のときは常に可能であり、したがってこの方法は、三角形の面を持つ任意の多面体グラフを実現するために使用できる。多面体グラフに三角形の面が含まれていない場合、その双対グラフには三角形が含まれており、多面体でもあるため、このように双対を実現し、その後、元のグラフを双対実現の極多面体として実現することができる。 ^{[4] [19]}リフティングを使用して多面体を実現する別の方法は、最大で 5 つの頂点を持つ任意の面を外面として選択することで双対性を回避する。すべての多面体グラフにはそのような面があり、この面の固定形状をより慎重に選択することで、グラフの残りの部分の Tutte 埋め込みを持ち上げることができる。^[20]

円充填定理の1つの変形によれば、すべての多面体グラフに対して、グラフの頂点と面を表す円の系が平面内または任意の球面上に存在し、次のようになります。

• グラフの隣接する2つの頂点は接線円で表され、
• グラフの隣接する2つの面は接線円で表され、
• 頂点とそれが接する面の各ペアは、直角に交差する円で表され、
• 他のすべての円のペアは互いに分離されています。^[21]

同じ円のシステムは、頂点を表す円と面を表す円の役割を入れ替えることで、双対グラフの表現を形成します。3 次元ユークリッド空間に埋め込まれた球面上のこのような表現から、境界が面円を通過する半空間の交差として、与えられたグラフと組み合わせ的に同等な凸多面体を形成できます。この多面体の各頂点から見ると、その頂点から見た球面上の地平線が、その頂点を表す円になります。この地平線の特性によって各頂点の 3 次元位置が決定され、多面体はこのように配置された頂点の凸包として同等に定義できます。球面は実現の中球になります。多面体の各辺は、2 つの接する頂点円が 2 つの接する面円と交差する点で、球面に接します。^[22]

任意の多面体グラフは、座標が整数である凸多面体によって実現できるという、より強力な形式の Steinitz の定理を証明することは可能です。^[23]たとえば、Steinitz の元の帰納法に基づく証明は、この方法で強化できます。ただし、Steinitz の構築から得られる整数は、与えられた多面体グラフの頂点の数に対して2 倍の指数関数的になります。この大きさの数値を2 進表記で書き表すには、指数関数的な数のビットが必要になります。^[19]幾何学的には、これは多面体の一部の特徴が他の特徴よりも 2 倍の指数関数的に大きい可能性があることを意味し、この方法から得られる実現は、グラフ描画への応用には問題があります。^[4]

その後の研究者は、頂点あたり線形数のビットのみを使用するリフティングベースの実現アルゴリズムを発見しました。^{[20] [24]}座標が整数であるという要件を緩和し、頂点の -座標が 0 から までの範囲の異なる整数であり、他の 2 つの座標が単位区間の実数であるような方法で座標を割り当てることも可能です。これにより、各辺の長さは少なくとも 1 になり、多面体全体の体積は線形になります。^{[25] [26]}一部の多面体グラフは、多項式サイズのグリッドでのみ実現可能であることが知られています。特に、ピラミッド (ホイール グラフの実現)、プリズム (プリズム グラフの実現)、および積み重ねられた多面体(アポロニアン ネットワークの実現) の場合に当てはまります。^[27]${\displaystyle x}$${\displaystyle 2n-4}$

整数実現の存在を述べる別の方法は、すべての3次元凸多面体には、組み合わせ的に同値な整数多面体があるということです。^[23]たとえば、正十二面体は、正五角形の面を持っているため、それ自体は整数多面体ではありませんが、同値な整数ピリトヘドロンとして実現できます。^[20]これは、整数同等物を持たない多面体（パールズ構成から構築されたものなど）が存在する高次元では常に可能であるとは限りません。 ^[28]

Halinグラフは多面体グラフの特殊なケースであり、平面埋め込み木(次数 2 の頂点なし) の葉を閉路に接続して形成されます。Halin グラフでは、特殊なタイプの多面体実現を選択できます。外側の閉路は水平の凸型ベース面を形成し、他のすべての面はベース面の真上に位置し (持ち上げによって実現される多面体の場合と同様)、これらすべての上部面の傾斜は同じです。任意のベース多角形 (必ずしも凸型ではない) 上の等傾斜面を持つ多面体表面は、多角形の直線スケルトンから構築できます。この実現を記述する同等の方法は、木のベース面への 2 次元投影がその直線スケルトンを形成するということです。この結果の証明には帰納法が用いられる。すなわち、すべての子が葉である内部ノードから葉を削除することで、任意の根付き木をより小さな木に縮小することができ、より小さな木から形成されるハリングラフは帰納法仮説によって実現され、この実現を修正することで、子が削除された木ノードに任意の数の葉の子を追加することができる。^[29]

与えられた多面体グラフ を表す任意の多面体において、 の面は、 のサイクルであり、2 つの要素に分離しないものである。つまり、 から面サイクルを削除すると、の残りの部分は連結されたサブグラフになる。このようなサイクルは周辺サイクルと呼ばれる。したがって、面の組み合わせ構造 (ただし、面の幾何学的形状ではない) は、グラフ構造から一意に決定される。 Barnette と Grünbaum による Steinitz の定理の別の強化では、任意の多面体グラフ、グラフの任意の面、およびその面を表す任意の凸多角形について、指定された面に対して指定された形状を持つグラフ全体の多面体実現を見つけることができると述べている。これは、すべての面が凸で、外面に対して任意の指定された形状を持つ平面に任意の多面体グラフを描くことができるという Tutte の定理に関連している。ただし、Tutte の方法によって生成される平面グラフの描画は、必ずしも凸多面体に持ち上げられるわけではない。代わりに、BarnetteとGrünbaumは帰納的方法を用いてこの結果を証明した。^[30]多面体グラフと内の任意のサイクルが与えられた場合、平行射影 の下での実現のシルエットを形成するの実現を見つけることも常に可能である。^[31]${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle C}$${\displaystyle G}$${\displaystyle C}$

円充填定理を用いた多面体の実現は、シュタイニッツの定理をさらに強化する。すなわち、3連結平面グラフはすべて、そのすべての辺が多面体の中心球である同じ単位球 に接するような凸多面体として表現できる。[ 22 ]^{円充填を多面体に変換する前に慎重に選択された}メビウス変換を実行することで、グラフのすべての対称性を実現する多面体実現を見つけることが可能であり、これはすべてのグラフ自己同型が多面体実現の対称性であるという意味で可能である。^{[32] [33]}より一般的には、が多面体グラフで が任意の滑らかな3次元凸体である場合、のすべての辺が に接するの多面体表現を見つけることが可能である。^[34]${\displaystyle G}$${\displaystyle K}$${\displaystyle G}$${\displaystyle K}$

円充填法は、すべての頂点を通る外接球面、またはすべての面に接する内接球面を持つ多面体のグラフを特徴付けるのにも使用できます。(外接球面を持つ多面体は、双曲幾何学では理想多面体としても重要です。) どちらの場合も、球体の存在は、グラフの各辺に関連付けられた正の実数変数に関する線形不等式の連立が解けることと同等です。内接球面の場合、これらの変数の合計は、グラフの各面サイクルで正確に 1 になり、面以外のサイクルでは 1 より大きくなければなりません。同様に、外接球面の場合、変数の合計は、各頂点で 1 になり、カットの各側に 2 つ以上の頂点がある各カット全体で 1 より大きくなければなりません。満たすべき線形不等式の数は指数的に多いかもしれませんが、楕円体法を使用して多項式時間で解 (存在する場合) を見つけることができます。解の変数の値は、対応する多面体が球と望ましい関係にある円充填における円のペア間の角度を決定します。^{[35] [36]}

3 次元を超える任意の次元では、アルゴリズム Steinitz 問題は、与えられた格子が凸多面体の面格子であるかどうかを判断することから構成されます。これはNP 困難であり、リヒター-ゲバートの普遍性定理により、4 次元多面体であっても実数の存在理論に対してより完全であるため、多項式時間計算量を持つ可能性は低いです。 ^[38]ここで、実数の存在理論は、与えられた多項式方程式と不等式のシステムを満たす実変数を見つけることによって定式化できる計算問題のクラスです。アルゴリズム Steinitz 問題の場合、そのような問題の変数は多面体の頂点座標であり、方程式と不等式を使用して、与えられた面格子の各面の平坦度と、面間の各角度の凸性を指定できます。完全性とは、このクラスの他のすべての問題が、多項式時間でアルゴリズム的シュタイニッツ問題の同等の例に変換できることを意味します。このような変換が存在するということは、アルゴリズム的シュタイニッツ問題が多項式時間で解けるのであれば、実数の存在理論のすべての問題とNPのすべての問題も多項式時間で解けることを意味します。^[39]しかし、与えられたグラフは複数の面格子に対応する可能性があるため、この完全性の結果を4次元多面体のグラフを認識する問題に拡張することは困難です。このグラフ認識問題の計算複雑性を決定することは未解決のままです。^[40]

研究者らは、3次元の非凸多面体^{[37] [41]}と4次元の凸多面体[ ^{40] [ 42]の特定の特殊なクラスのグラフのグラフ理論的特徴付けも発見した。 [43]}しかし、どちらの場合も、一般的な問題は未解決のままである。実際、どの完全グラフが非凸多面体のグラフであるかを決定する問題さえも未解決のままである（四面体とチャーサール多面体を除く）。^[44]${\displaystyle K_{4}}$${\displaystyle K_{7}}$

エバーハルトの定理は、凸多面体の面を形成するために組み合わせることができる多角形の多重集合を部分的に特徴付ける。これは、与えられた多角形の面の集合で3連結平面グラフを形成し、次にシュタイニッツの定理を適用してそのグラフの多面体実現を見つけることによって証明できる。^[3]

László Lovász は、グラフの多面体表現と、同じグラフのColin de Verdière グラフ不変量を実現する行列との間の対応関係を示しました。 Colin de Verdière 不変量は、多面体グラフには関係のないいくつかの追加条件の下での、グラフの重み付き隣接行列の最大コランクです。これらは、頂点でインデックス付けされた正方対称行列で、頂点の重みは対角係数に、辺の重みは非対角係数とに含まれます。頂点とが隣接していない場合、係数は0 である必要があります。この不変量は、グラフが平面グラフである場合に限り、最大で 3 になります。ロヴァースが示すように、グラフが多面体の場合、そのグラフを多面体として表現するには、共階数3の重み付き隣接行列を見つけ、そのヌル空間の基底を形成する3つのベクトルを見つけ、これらのベクトルの係数を多面体の頂点の座標として使用し、これらの頂点を適切にスケーリングします。^[45]${\displaystyle i}$${\displaystyle M_{i,i}}$${\displaystyle i,j}$${\displaystyle M_{i,j}}$${\displaystyle M_{j,i}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle M_{i,j}}$

シュタイニッツの定理の歴史はグリュンバウム（2007）^[46]によって説明されており、彼はこの定理が1916年に最初に書かれたエルンスト・シュタイニッツの出版物に難解な形で初めて登場したと述べています。 ^[6]シュタイニッツは、1928年の死後に出版された後の講義ノートでより詳細な情報を提供しています。シュタイニッツの定理の現代的な扱いは、これを多面体のグラフ理論的特徴付けであるとしていますが、シュタイニッツはグラフの言語を使用していませんでした。^{[46]この定理のグラフ理論的定式化は、1960年代初頭に}ブランコ・グリュンバウムとセオドア・モツキンによって導入され、その証明もグリュンバウムの1967年のテキストConvex Polytopesでグラフ理論に変換されました。^[46] ΔY変換とYΔ変換に関するエピファノフの研究は、シュタイニッツの証明を強化するものであり、多面体の特徴付け以外の問題に動機づけられたものである。トゥルーエンパー（1989）は、この研究がシュタイニッツの定理と関連していることに気づいたのはグリュンバウムのおかげだとしている。^[11]

応力図と多面体リフティング間のマクスウェル-クレモナ対応は、ピエール・ヴァリニョン、ウィリアム・ランキンらの初期の業績に基づいて、1864年から1870年にかけてジェームズ・クラーク・マクスウェルが一連の論文で展開し、19世紀後半にルイジ・クレモナによって普及した。^{[47]この対応を}タッテ埋め込みと組み合わせてシュタイニッツの定理を証明できるという観察は、イーデスとガーバン（1995）によるものである。^[4]また、リヒター-ゲバート（1996）も参照。^[38]

円充填定理は1936年にポール・ケーベによって証明され^{[48] [49]}、1970年には（独立に）EM・アンドレーエフによって証明された。 ^{[49] [50]}この定理は1980年代半ばにウィリアム・サーストンによって広められたが、サーストンは（ケーベとアンドレーエフを引用しているにもかかわらず）この定理の発見者の一人としてしばしば認められている。^[49]アンドレーエフのバージョンの定理は、双曲空間内の特定の多面体に対するシュタイニッツのような特徴付けとして既に定式化されており[ 50 ^]、円充填を使用して中球を持つ多面体を実現することはサーストンの研究に由来する。^[51]内接球または外接球を持つ多面体を特徴付ける問題は、最終的には円充填実現に基づく方法を使用して解決され、1630年頃のルネ・デカルトの未発表の研究^[52]と1832年のヤコブ・シュタイナーにまで遡ります。^{[35] [53]}内接球または外接球で実現されていない多面体の最初の例は、1928年にシュタイニッツによって示されました。^{[35] [54]}