クラスカル法の正当性の証明

蟻本を読んでいたら、クラスカル法の正当性の証明が省略されていたので、自分で証明を構築してみた。 誰かの役に立つといいな。

ちなみにTeXで書く元気はなかった。汚くてごめんなさい。

---

クラスカル法の正当性の証明

連結な無向グラフG上のクラスカル法を考える。

X0=∅とし、これに閉路ができないように貪欲的にコスト最小の辺を付け加えていってできるGの部分グラフをX1, X2,..., Xnとする(これ以上辺を付け加えると 必ず閉路ができるグラフがXnである)。 以下、XnがGの最小全域木であることを示す。

まず、

S = {X | Xを部分グラフとするGの最小全域木が存在する}

とする。このとき、Xk∈S(k=0,...,n)を帰納法により示す。

まず、X0∈Sはよい。以下、Xk∈Sを仮定してX(k+1)∈Sを示す(k<nとする)。

帰納法の仮定よりXk∈Sであるから、Xkを部分グラフとするGの最小全域木Tが存在する。 Xkに含まれず、Xkに付け加えても閉路ができないコスト最小の辺をe=(u,v)とする。 e∈Tならば自明にX(k+1)∈Sであるから、e∉Tとする。

Tは木であるから、T'=T∪{e}とすると、T'には閉路ができる。 このとき、閉路に含まれる辺で、Xkに含まれず、eと異なる辺fが存在する。 [もし存在しないならば、閉路に含まれる辺はe以外全てXkに含まれるので、Xkにeを付け加えると閉路ができてしまい矛盾する。] fはXkに含まれず、またf∈TよりXkにfを付け加えても閉路はできないから、eの取り方より

cost(e) ≦ cost(f). ・・・(1)

TはGの全域木であったから、T''=T'-{f}=T∪{e}-{f}もGの全域木である。 さらに式(1)より、cost(T'')≦cost(T).故にT''はGの最小全域木である。すなわちX(k+1)∈S. 以上により、Xk∈S => X(k+1)∈Sが示された。

以上から、数学的帰納法によりXk∈S(k=0,...,n)が、特にXn∈Sが示された。

最後に、XnがGの最小全域木であることを示す。 まず、Xn∈Sであるから、Xnを部分グラフとするGの最小全域木Tが存在する。 このときcost(Xn)≦cost(T)であるから、もしXnがGの全域木であれば、同時に最小全域木でもあることが言える。 故に、XnがGの全域木であることを言えば良い。 すなわち、Xnは閉路のない連結なグラフで、Gの全ての頂点を含んでいることを言えば良い。

○閉路がなく連結であること

閉路がないことは、Xkの取り方からよい。連結であることを示す。 仮にXnが連結でなかったとすると、Xnは最低でも２つの連結成分に分けられる。 Gは連結であるから、それらを結ぶ辺eが存在する。このときXnにeを付け加えても閉路が出来ないが、これはXnの定義に反する。 故にXnは連結である。

○Gの全ての頂点を含んでいること

仮にXnに含まれないGの頂点vが存在したとする。 Gは連結であるから、vとXnを結ぶ辺eが存在する。このときXnにeを付け加えても閉路が出来ないが、これはXnの定義に反する。 故にXnはGの全ての頂点を含んでいる。

以上より、XnがGの全域木であり、したがって最小全域木であることが示された。（証明終）