双対グラフによる証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/19 22:04 UTC 版)
「オイラー標数」の記事における「双対グラフによる証明」の解説
まず、多面体の頂点や辺の関係は平面グラフに落とし込むことができることに着目する。これは次のようにして可能である。まず多面体の面の一つを取り除き、空いた穴を広げて残りの面を平面に近づけていく。こうしてできたグラフの外側の領域を最初に取り除いた面と対応させれば、多面体の頂点と辺の関係を持つ平面グラフが得られる。次に、平面グラフの全域木とその双対を考える。グラフの全域木とはグラフのすべての頂点を接続し、なおかつ閉路を含まないようなグラフである。また、双対グラフとは、元となるグラフの面に対応する頂点をもち、元グラフの面どうしを繋ぐ辺に対応する辺をもつグラフである。全域木の双対は、元グラフの双対のうち、全域木に含まれない辺に対応する辺を含むグラフである。全域木の双対は元グラフの双対の全域木となることは、以下のようにしてわかる。 いま、平面グラフGとその双対G*を考える。Gの全域木Sに対し、GのうちS に含まれないグラフを~Sとする。また、G*のうち~Sに対応するグラフを~S*とする。Sは閉路を持たないため、Gの各々の面を囲む辺のうち、少なくとも1つは~Sに含まれる。このことを双対の世界で言い直すと、G*の各頂点は必ず~S*がもつ辺により連結されるということになる。ここでもし~S*が閉路を持つとすると、同様の議論によって、Gの頂点のうち少なくとも1つがSにより連結されないことになる。しかし、これはSが全域木であることと相容れないため、~S*は閉路を持たない。よって、~S*はG*の全ての頂点を連結し、閉路を持たない。すなわち~S*はG*の全域木である。 このことから、平面グラフの全ての辺は全域木と、グラフの双対の全域木に対応する辺に分解することができる。 木グラフは一つの頂点から初めて、頂点と辺をそれぞれ一つずつグラフに付け加えていくことによって作ることができる。このため、木グラフの頂点の数Vと辺の数Eは、E = (V − 1) という関係をもつ。いま、グラフGについてその全域木Sが与えられたとする。Sの辺の数をESとすると、ES = (V − 1) が成り立つ。またSの双対~S*の辺の数をE~S*とすると、~S*はG* の全域木であるため、G*の頂点の数、すなわちGの面の数Fについて同様な関係 E~S* = (F − 1)が成り立つ。Sの辺の数と~Sの辺の数を足すとGの辺の数に等しく、また~Sの各辺は~S*の各辺に一対一に対応するため、 E = (V − 1) + (F − 1) が成り立つ。これはオイラーの公式に他ならない。
※この「双対グラフによる証明」の解説は、「オイラー標数」の解説の一部です。
「双対グラフによる証明」を含む「オイラー標数」の記事については、「オイラー標数」の概要を参照ください。
- 双対グラフによる証明のページへのリンク
