全域木とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/10 17:55 UTC 版)

「クラスカル法」の記事における「全域木」の解説

重み付き連結グラフ P {\displaystyle P} があり、クラスカル法で生成した P {\displaystyle P} の部分グラフを Y {\displaystyle Y} とする。常に異なる2つの木を連結する辺を加えているので、 Y {\displaystyle Y} には閉路がない。また、 Y {\displaystyle Y} の2つの部分を連結する辺を全て選んでいるので、全頂点は連結されている。したがって Y {\displaystyle Y} は P {\displaystyle P} の全域木である。

※この「全域木」の解説は、「クラスカル法」の解説の一部です。
「全域木」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)

「双対グラフ」の記事における「全域木」の解説

全域木は、グラフのすべての頂点を含む、連結された非巡回サブグラフとして定義できる。ここで、平面グラフGとその双対G*を考える。Gの全域木Sに対し、GのうちS に含まれないグラフを~Sとする。また、G*のうち~Sに対応するグラフを~S*とする。このとき~S*はG*の全域木となる。これは次のようにして分かる。Sはサイクルを持たないため、Gの各々の面を囲む辺のうち、少なくとも1つは~Sに含まれる。このことを双対の世界で言い直すと、G*の各頂点は必ず~S*がもつ辺により連結されるということになる。ここでもし~S*がサイクルを持つとすると、同様の議論によって、Gの頂点のうち少なくとも1つがSにより連結されないことになる。しかし、これはSが全域木であることと相容れないため、~S*はサイクルを持たない。よって、~S*はG*の全ての頂点を連結し、サイクルを持たない。すなわち~S*はG*の全域木である。 このことから、平面グラフの全ての辺は全域木と、グラフの双対の全域木に対応する辺に分解することができる。 このタイプの分解の例は、単純な格子の辺の一部を壁としたようなタイプの迷路で見ることが出きる。このような迷路では壁とその間の空間は互いに入れ子になった木構造を形成する。この木構造は元の格子が形成するグラフの全域木とみなせる。このとき空間が構成する木構造は、元のグラフの双対の全域木となる。 このような2つの木構造への分解は、オイラーの公式の単純な証明を与える。木構造において、頂点の数Vと辺の数Eは、E = (V − 1) という関係をもつ。このことは次のようにして分かる。木構造は一つの頂点から初めて、新しい頂点と辺を加えていくことで作ることができる。この操作のはじめはE = 0,V = 1であり、その後E,Vが同数ずつ増えていく。このことから上式が成り立つことがわかる。 いま、グラフGについてその全域木Sが与えられたとする。Sの辺の数をESとすると、ES = (V − 1) が成り立つ。また~S*の辺の数をE~S*とすると、~S*はG* の全域木であるため、G*の頂点の数、すなわちGの面の数Fについて同様な関係 E~S* = (F − 1)が成り立つ。Sの辺の数と~Sの辺の数を足すとGの辺の数に等しく、また~Sの各辺は~S*の各辺に一対一に対応するため、 E = (V − 1) + (F − 1) が成り立つ。これはオイラーの公式に他ならない。Duncan Sommervilleによると、オイラーの公式のこの証明はK. G. C. Von Staudtの Geometrie der Lage（Nürnberg, 1847）による。 非平面表面埋め込みでは、全域木と相補的な双対辺は元のグラフの全域木とはならない。そのかわり、これらは元のグラフの双対の全域木と少数の余分な辺を合わせた集合となる。このとき、余分な辺の数は、グラフが埋め込まれている曲面の種数によって決まる。この余分な辺は全域木に含まれる経路と合わせて用いることで、曲面の基本群を生成できる。

※この「全域木」の解説は、「双対グラフ」の解説の一部です。
「全域木」を含む「双対グラフ」の記事については、「双対グラフ」の概要を参照ください。