グラフ理論における全域木とは？その求め方

どうも、木村（@kimu3_slime）です。

今回は、グラフ理論における全域木とは何か、その求め方を紹介します。

全域木とは
全域木の求め方
こちらもおすすめ

全域木とは

ある地域に、次のグラフで示すようなネットワークを組みたいとしましょう。辺を通じて、情報や電気などが伝わるとします。

通信網の建設には、ある程度のコストがかかるとします。そこで、全頂点がつながったまま、全体がつながるような辺の残し方はできないでしょうか。つまり、頂点を保ったままサイクルを持たない連結なグラフ（木）を求める問題、これが全域木の問題です。

\(G=(V,E)\)を抽象グラフとします。\(E^{\prime }\subset E\)として、\(G^{\prime}=(V,E^{\prime})\)が木となるとき、\(G^{\prime}\)をグラフ\(G\)の全域木（spanning tree）と呼びます。スパニング木とも。spanは数学では生成するという意味を持つので、グラフを生成する木、生成木と呼びたいですね。

例えば、さきほどのグラフから点線で表した辺を除けば、サイクルを持たないグラフ、すなわち木になっています。これが元のグラフの全域木です。全域木は、元の頂点をすべて含んだ木であるような部分グラフです。

木は連結なので、元のグラフが連結でなければ当然全域木を見つけることはできません。

全域木の求め方

すべての連結なグラフには、全域木が存在します。全域木の構成方法はいくつか知られていますが、そのひとつを紹介しましょう。

全域木の求め方

\(G=(V,E)\)を連結なグラフで、頂点数を\(n\)、辺数を\(m\)とする。辺に適当に番号をつけて、\((e_1,e_2,\dots,e_m)\)と表す。

辺の集合の拡大列\(E_0,E_1,\dots,E_T\)を作る。構成の手順は次の通り。

\(E_0 = \varnothing\)とする。
\(i<m\)のときは次のように辺を増やす。
1. \[ \begin{aligned}E_i= \begin{cases}E_{i-1}\cup \{e_i\} & ((V,E_{i-1}\cup \{e_i\})がサイクルを持たない )\\E_{i-1} & (それ以外)\end{cases}\end{aligned} \]
\(i=m\)ならば停止する。そのときの辺の集合を\(E_T\)とする。

得られたグラフ\(G^{\prime}=(V,E_T)\)が全域木である。

この方法で全域木が作れるか試してみましょう。まず、辺に適当に番号をつけます。