12.11 森と木

これまで本書では非巡回有向グラフを何度も使ってきた。しかし、情報科学で最も重要なグラフは間違いなく非巡回単純グラフである。

例えば図 \(\text{12.18}\) のグラフは森であり、その連結成分は定義より木である。

12.11.1 葉

いくつか森を観察すると、多くの森には次数が \(1\) の頂点が存在する事実に気が付くだろう。

図 \(\text{12.18}\) の森は \(4\) 個の葉を持ち、図 \(\text{12.19}\) の木は \(5\) 個の葉を持つ。

孤立頂点を持つ森は、頂点が \(1\) 個でない限り木にならない。よって連結な森 ── つまり木 ── が \(2\) 個以上の頂点を持つとき、その葉の次数は \(1\) と分かる。葉が多く存在するわけではない: 線グラフ \(L_{n}\) は木であり、葉を \(2\) 個しか持たない。ただ、この値は最小値である:

証明 \(T\) を有限木とする。\(T\) に含まれる最長の路を一つ取って \(\textbf{p}\) として、\(\textbf{p}\) の終点を \(u\) とする。\(u\) を端点に持つ辺であって \(\mathbf{P}\) に含まれないものが存在するなら、その辺を \(\mathbf{P}\) に付け足すことで最長の路を伸ばすことができる。しかし \(\textbf{p}\) は \(T\) の最長の路なので、そのような辺は存在しない。

\(T\) は \(2\) 個以上の頂点を持つので、最長の路 \(\textbf{p}\) は少なくとも一つの辺を含む。よって最後の辺 \(\langle v\>\text{---}\>u \rangle\) が存在する。もし \(\textbf{p}\) に含まれる頂点 \(w \neq v\) と \(u\) を結ぶ辺が存在するなら、\(w\) から \(\textbf{p}\) をたどって \(u\) に到達し、そこから \(w\) に戻ることで閉路を構成できる。しかし \(T\) は木だから、そのような辺は存在しない。

以上より \(\langle v\>\text{---}\>u \rangle\) は \(u\) に接続する唯一の辺だと分かる。言い換えれば \(u\) は葉である。\(\textbf{p}\) の始点も同様の議論で葉だと示せる。 ■

12.11.2 木の性質

木を特徴付ける性質は数多く知られている。これは木が様々な場面で現れる理由の一つと言える。

証明 これから \(4. \longrightarrow 2. \longrightarrow 1. \longrightarrow 3. \longrightarrow 4.\) を示す。最後のものを除けば、どの含意も簡単に示せる。

• [\(4. \longrightarrow 2.\)] 連結性は \(4.\) より明らかである。

  \(\langle u\>\text{---}\> v \rangle\) を \(G\) の辺とする。辺として \(\langle u\>\text{---}\> v \rangle\) だけを含む路は \(u\) と \(v\) を結ぶ唯一の路である。よって \(G\) から辺 \(\langle u\>\text{---}\> v \rangle\) を削除したグラフには \(u\) と \(v\) を結ぶ路は存在せず、\(u\) と \(v\) は連結でない。

• [\(2. \longrightarrow 1.\)] 連結性は \(2.\) より明らかである。閉路に含まれる辺はカット辺でない (補題 12.10.3) ので、全ての辺がカット辺のグラフは閉路を持たない。

• [\(1. \longrightarrow 3.\)] 連結性より、任意の異なる二頂点 \(u\), \(v\) を結ぶ路が存在する。よって \(u\) と \(v\) が隣接しないとき、\(u\), \(v\) を結ぶ路に辺 \(\langle u\>\text{---}\>v \rangle\) を加えると閉路が生まれる。

• [\(3. \longrightarrow 4.\)] 二頂点を結ぶ異なる路が二つあるとき、二頂点を dpp (different-path-pair, 異なる路を持つ組) と呼ぶことにする (問題 12.35 で見るように、dpp に含まれる頂点が閉路に含まれない可能性があることに注意する)。\(G\) に dpp が存在すると仮定して矛盾を導く。

  二頂点を結ぶ路の長さが最小の dpp を \(u\), \(v\) として、その長さ最小の路を \(\textbf{p}\) とする。\(u\), \(v\) は dpp より、\(u\) と \(v\) を結ぶ \(\textbf{p}\) でない路 \(\textbf{q}\) が存在する。

  \(\textbf{p}\) と \(\textbf{q}\) が端点 \(u\), \(v\) 以外に共通の頂点 \(w\) を通るなら、\(u\), \(w\) または \(w\), \(v\) が dpp となる。しかし \(u\) と \(w\) および \(w\) と \(v\) を結ぶ路はいずれも \(\textbf{p}\) より短いので、\(\textbf{p}\) の最小性と矛盾する。よって \(\textbf{p}\) と \(\textbf{q}\) は端点以外に頂点を共有しない。よって二つの路を連結すると閉路を構築できるものの、これは \(\text{3.}\) と矛盾する。

■

定理 12.11.4 の同値性は無限木に対しても成り立つ¹。有限木に対しては、頂点の個数と辺の個数に関する有用な特徴付けがさらに二つ存在する。

証明 頂点の個数 \(n\) に関する数学的帰納法を用いる。次の述語 \(P(n)\) を帰納法の仮定とする:

ベースケース: \(n = 1\) のとき、\(F\) は \(1\) 個の孤立頂点だけを持つ。このとき \(|E(F)| = 0\) であり、\(P(1)\) は成り立つ。

帰納ステップ: ある \(n \geq 1\) で \(P(n)\) が成立すると仮定する。これから \(P(n + 1)\) を示す。

\(F\) が孤立頂点 \(v\) を持つとき、\(F\) から頂点 \(v\) を除去したグラフ \(F - v\) は \(n \geq 1\) 頂点の森である。よって帰納法の仮定より、\(F - v\) は \(n - |E(F - v)| = n - |E(F)|\) 個の木から構成される。\(v\) は孤立頂点なので、\(F\) は \((n + 1) - \left| E(F) \right|\) 個の木から構成される。つまり \(P(n + 1)\) は成り立つ。

\(F\) が孤立頂点を持たないとき、\(F\) の各連結成分は \(2\) 個以上の頂点を持つ。\(T\) を \(F\) の連結成分 (木) とする。補題 12.11.3 より、\(T\) には次数が \(1\) の葉 \(v\) が存在する。\(F\) から頂点 \(v\) と \(v\) に接続する唯一の辺を除去したグラフを \(F - v\) とする。頂点と辺の除去で閉路が生まれることはないので、\(F - v\) は \(n\) 頂点の森である。そして、\(F - v\) の連結成分は \(T\) を除いて \(F\) の連結成分と同じであり、\(T\) は (\(F - v\) と同様に定義される) \(T - v\) となる。特に、\(F\) と \(F - v\) は同じ個数の連結成分を持つ。

帰納法の仮定より、\(F - v\) の連結成分の個数は

と分かる。つまり \(F\) は \((n + 1) - |E(F)|\) 個の連結成分を持ち、\(P(n + 1)\) は成り立つ。 ■

証明 \(1. \longrightarrow 2. \longrightarrow 3. \longrightarrow 1.\) を示す。

• [\(1. \longrightarrow 2.\)] 有限木は \(1\) 個の連結成分を持つ有限森なので、定理 12.11.5 から直ちに \(2.\) を得る。

• [\(2. \longrightarrow 3.\)] 定理 12.11.5 より、有限森 \(G\) は \(|V(G)| - |E(G)| = 1\) 個の連結成分を持つ。連結成分の定義より \(G\) は連結である。

• [\(3. \longrightarrow 1.\)] \(G\) が有限かつ連結で \(|V(G)| = |E(G)| + 1\) を満たす仮定する。このとき \(G\) の閉路に含まれる辺からなる集合 \(E \subseteq E(G)\) であって、\(G\) から \(E\) を除去して残るグラフ \(G - E\) が連結かつ非巡回になるものが存在する。\(G - E\) は連結成分を \(1\) 個しか持たないので、定理 12.11.5 から次の等式が分かる:

  \[ \begin{aligned} 1 &= |V(G-E)| - |E(G - E)| \\ &= |V(G)| - (|E(G)| - |E|) \\ &= (|V(G)| - |E(G)|) + |E| \\ &= 1 + |E| \qquad (|V(G)| = |E(G)| + 1 \text{ より}) \end{aligned} \]

  ここから \(|E| = 0\) を得る。つまり \(G\) は最初から非巡回である。

■

12.11.3 全域木

木はそこら中にある。例えば、全ての連結グラフは同じ頂点集合を持つ木を部分グラフに持つ。この木はグラフの全域木 (spanning tree) と呼ばれる。図 \(\text{12.20}\) にグラフとその全域木の例を示す。赤い辺で示された部分グラフが全域木の一つを表す。

証明 \(G\) を有限連結グラフとする。このときグラフ \(G\) 自身は連結な全域部分グラフである。よって整列原理より、\(G\) は辺の個数が最小な連結全域部分グラフ \(T\) を持つ。定理 12.11.4 の \(\text{2.}\) より、\(T\) は木である。 ■

12.11.4 最小重み全域木

全域木は重み付きグラフ (辺に数値が割り当てられたグラフ) を考えるとき特に興味深く重要になる。重み付きグラフの重み (weight) は辺の重みの和と定義される。例えば図 \(\text{12.21}\) \(\text{(a)}\) に示された全域木の重みは \(19\) である。

一般に、重みが最も小さくなる全域木を見つけることが目標となる場合が多い。この全域木を最小重み全域木 (minimum-weight spanning tree, MST) と呼ぶ。

図 \(\text{12.21}\) \(\text{(a)}\) の全域木は図 \(\text{12.21}\) \(\text{(b)}\) のグラフの MST ではない: 図 \(\text{12.22}\) に示す重み \(17\) の全域木が存在する。このグラフに重みが \(17\) より小さい全域木は存在しないのだが、それはどうすれば証明できるだろうか？ さらに、一般の連結グラフ \(G\) の MST はどうすれば構築できるだろうか？ \(G\) の部分木を一つずつ全て試す方法も考えられるものの、その方法だと大規模なグラフは手に負えなくなる。

これから本節では、\(G\) が連結な重み付きグラフだと仮定する。これから \(G\) の MST を構築する単純かつ一般的な方法を説明する。

証明 分割のブロックは定義より非空である。よって \(G\) の任意の白黒彩色は少なくとも一つの白頂点と少なくとも一つの黒頂点を持つ。加えて \(G\) は連結なので、\(G\) には黒頂点から白頂点への路が存在する。その路には黒頂点と白頂点を結ぶ辺が含まれ、それが灰色辺である。 ■

これまでに例として示してきた重み付きグラフでは、同じ重みを持つ複数の辺が存在した。これは実際の応用でもよくある。しかし、重みが全て異なると仮定すると議論が簡単になる。そこで:

全ての辺が異なる重みを持つと仮定しても一般性は失われない。なぜなら、各辺に番号を一意に割り当て、同じ重みの二辺は番号が大きい方が「重い」と定めるのと同じことだからである。

この仮定があると、MST は次の補題を使って簡単に構築できる。証明は後回しとする:

つまりグラフ \(G\) の MST を構築するには、辺の無いグラフから始めて任意に選んだ白黒彩色における重みが最小の灰色辺を加えていけばよい。具体的には次の通りである:

証明 一般化された最小重み灰色辺アルゴリズムの繰り返し処理が実行されるときグラフ \(S\) は連結でないので、選択される白黒彩色は \(S\) に含まれる任意の辺の端点に同じ色を割り当てる。よって任意の灰色辺は \(S\) に含まれず、\(S\) に追加される重みが最小の灰色辺も \(S\) に含まれない。

補題 12.11.10 より選択される白黒彩色には少なくとも一つの灰色辺が存在し、従って³重みが最小の灰色辺も存在する。\(S\) に一本の灰色辺を加えると、\(S\) の連結成分の個数が \(1\) だけ減少する。よって \(G\) の頂点数を \(n\) とすれば、初期状態の \(S\) に \(n - 1\) 本の灰色を加えた時点で \(S\) は連結になって停止する。停止するとき \(S\) は \(n-1\) 本の辺を持つ連結なグラフだから、定理 12.11.6 の \(\text{3.}\) より木でもある。 ■

灰色辺補題 (補題 12.11.11) からは、このアルゴリズムが構築する MST \(T\) の任意の辺は \(G\) の全ての MST に含まれると分かる。これは全ての MST が \(T\) と同じ辺を持つ、つまり \(T\) と等しいことを意味する。言い換えれば、\(G\) は \(T\) の他に MST を持たない:

一般化された最小重み灰色アルゴリズムの特殊ケースには名前が付いているものがある:

Prim のアルゴリズムは \(S\) の頂点を白く、それ以外の頂点を黒く塗る白黒彩色を常に用いる特殊ケースである。この白黒彩色における灰色辺の端点はちょうど一方が \(S\) に属する。

「辺 \(e\) を \(S\) に追加したとき閉路が生じない」と「\(e\) の両端点が \(S\) の異なる成分に属する」は同値である。つまり Kruskal のアルゴリズムでは、\(S\) の異なる連結成分を結ぶ辺の中で重みが最小のものが追加される。

このアルゴリズムでは、離れた場所にある連結成分を並列かつ独立に成長させることができる。これは限られた通信しかできない複数のプロセッサが個別に処理を進める分散計算で役立つ性質である⁴。

最後に補題 12.11.11 を証明しよう。ある白黒彩色で重みが最小の灰色辺は必ず全ての MST に含まれることを示すために、次の補題を証明する:

証明 重みが最小の灰色辺が \(e\) である白黒彩色を固定する。\(C\) は連結な全域グラフなので、\(e\) の両端点を結ぶ路 \(\textbf{p}\) が \(C\) に存在する。この路 \(\textbf{p}\) は異なる色が塗られた二点 (\(e\) の両端点) を結ぶので、灰色の辺 \(g \neq e\) を少なくとも一つ含む。\(e\) は重みが最小の灰色辺より \(\operatorname{weight}(e) < \operatorname{weight}(g)\) が成り立つ。

続いて \(\textbf{p} + e\) が閉路である事実に注目する。この閉路から \(g\) を除去したとしても、\(g\) の両端点は閉路の残りの部分で接続される。これは \(C - g + e\) が連結であることを意味する。つまり、この \(g\) は二つの条件を満たす。 ■

灰色辺補題 (補題 12.11.11) は灰色辺交換補題 (補題 12.11.14) から直ちに得られる: \(C\) が \(G\) の全域木で \(e\) を含まないとき、\(C - g + e\) は \(C\) より重みが小さい全域木となる。よって \(C\) は \(e\) を含まない限り MST になれない。

参考文献

[9], [15], [24], [27], [29]