第４講 3-多面体のシュタイニッツの定理

グラフGが３次元多面体のグラフであるのは、単純で、平面的で、さらに3-連結であるときであり、かつそのときに限る。

2-connected(2-連結、１個の頂点とそれに接続するすべての辺を取り除いても、非連結にならないグラフ)、3-connected(3-連結、１個または２個の頂点とそれに接続するすべての辺を取り除いても、非連結にならないグラフ)…n-connected(n-連結)

平面的グラフの球面への埋め込みと双対グラフ(dual graph)

直並列還元(直列還元と並列還元)

双対性と変形の関係。埋め込まれた平面的グラフ⇔双対グラフ、直列辺の縮約⇔並列辺の除去、k-連結⇔k-連結、非分離三角形⇔三星、Δ-to-Y変形⇔Y-to-Δ変形

デルタ-Y変形(Δ-to-Y変形、Y-to-Δ変形)

平面的グラフはΔY還元可能’辺数４以上の3-連結平面的グラフはΔY変形の繰り返しによりK4グラフに還元できる)

シュタイニッツの定理

任意の3-多面体Pの実現空間は可縮(穴が空いていない)であり、したがって連結である(3-多面体を実現するための座標の与え方の全体のなす空間は連結である)。

正しい描画：各辺の力がすべて正の場合には平衡点が必ず凸の領域を与えることが知られているが、同一の性質のゴムひもで張ることを考えて、その平衡点に頂点を置くような描き方のこと

3-連結平面的グラフの場合、描画が正しいとき、かつそのときに限って、３次元空間に持ち上げることができる。