僕は、最小全域木を求めるKruskal法をココロから納得するのにとても長い時間が掛かってしまいました。本記事では、備忘録的な目的を兼ねて、少しKruskal法について書いてみたいと思います。
僕は、Kruskal法は今年5月頃初めて知ったのですが、そのときはどうしてコレで最小全域木が求まるのか、不思議でなりませんでした。その後6月頃にアルゴリズムイントロダクションを読んで、ひとまず証明は理解したのですが、イマイチなかなかイメージが掴めませんでした。さらに7月にはマトロイドの触りを勉強し、マトロイドのGreedyアルゴリズムからKruskal法が自然に導かれることを学んだのですが、それでもまだKruskal法をココロから納得するには至れませんでした。
それくらい、Kruskal法を納得するのにとても苦労しました。ようやく自分なりにKruskal法が納得できるようになったのは、マトロイドの交換公理についての学びを経て、最小全域木問題の最適性条件をハッキリと意識するようになってからでした。
思うに、最小全域木問題に限らず、最適化問題を考えるときには、「最適性条件を意識すること」が大事ではないかと思います。一番身近なところでは、上に凸な関数f(x)の最大値を求めるときの最適性条件は、f(x) = 0で与えられます。他にもとても多くのGreedyな問題は、最適性条件を意識することによって自然に思い付けるのではないかと考えています。最小全域木問題についても、最適性条件をしっかり意識することによってやっとKruskal法が自然なものに思えるようになりました。
なお、最小全域木を求める様々なアルゴリズムが、fura_2さんの最小全域木の特集にて、紹介されています。
全域木の構造
まずは、そもそも全域木の持っている構造について考えます。まずは全域木の基本的な構造です。
グラフGの全域木Tがあったとき、Tに含まれない辺eを選ぶと、T + {e}は閉路を1つ含みます。コレをTとeに関する基本閉路と呼び、C(T,e)と書きます。
また、Tに含まれる辺fを選ぶと、T - {f}は2つの全域木に分かれます(下図の黄色頂点と橙頂点)。このとき、グラフG全体のカットが1つ定まります。コレをTとfに関する基本カットと呼び、C*(T,f)と書きます。
そして、この基本閉路と基本カットを用いると、以下のようなキレイな構造が見えて来ます。
無向グラフGが与えられる。T, SをGの2つの全域木とする。
このとき、任意の e T-Sに対し、ある f
S-Tが存在して、
T - {e} {f}と、S
{e} - {f}とが共に全域木となる。
コレは次のようなことです。最初は、SとTはともに全域木です。このとき、Sは自分が持っていながTが持っている辺eを欲しがったとします。このとき、逆にSは持っているけどTは持っていない辺fが上手い具合にあって、SとTとでeとfとを交換することができます。交換しても、新Sと新Tはともに全域木となります。
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
証明は基本閉路と基本カットの構造をイシキすれば簡単です。
- T君はSにeをねだられたので、まずTにとってのeによる基本カットC*(T,e)を考えます。
- 反対にSはeが加わることで生じる基本閉路C(S,e)を考えます。
- これらは2つ以上の交辺を持ちますが、そのうちe以外の交辺をfとします。
- SとTとで、eとfを交換することで、上手いこと必ずSとTは新しい全域木になります。
最小全域木問題の最適性条件
さて、最小全域木問題の最適性条件について考えます。
ここまでに見た全域木の交換の構造を考えると、以下のとても嬉しい性質を示すことができます。この性質を見ると、もはやKruskal法は自然です。何故なら、Kruskal法による出力結果は、アルゴリズムの性質上必ず2の条件を満たすからです。
無向連結グラフGが与えられ、各辺eの重みをw(e)とする。またSをGの全域木とする。このとき、以下は同値である。
- TはGの最小全域木である
- Tに含まれない任意の辺eについて、基本閉路C(T,e)の任意の辺をfとすると、w(e) >= w(f)
（証明）
1→2は自明です。何故なら、Tに含まれないある辺eについて、あるf C(T,e)が存在してw(e) < w(f)であると仮定すると、Tはfを捨ててeを取り入れることによって、より重みの小さな全域木となって矛盾するからです。
2→1は以下のようにします。
まず、「Tに含まれない任意の辺eについて、基本閉路C(T,e)の任意の辺をfとすると、w(e) >= w(f)」を満たす全域木Tを取り、さらに任意の全域木をSとします。このとき、w(T) <= w(S)となることを|S-T|についての帰納法によって示します。まず、|S-T| = 0については、そもそもS = Tとなるので明らかです。
|S-T| <= n-1については正しいと仮定して、|S-T| = nについても正しいことを示します。
Sに含まれるがTには含まれない任意の辺eについて、基本閉路C(T,e)と基本カットC*(S,e)を考え、これらのe以外の交辺をfとする。このとき、C(T,e)についての条件より、w(e) >= w(f)が成立する。よって、SとTとでeとfを交換することにより、Sは新しくSになるとすると、w(S
) = w(S) - w(e) + w(f) <= w(S)となる。一方、|S
-T| = n-1となるので、帰納法の仮定より、w(T) <= w(S
)となるので、結局、w(T) <= w(S)が導かれます。//
結び
僕はKruskal法を知ってから長い間、どうしてこんな上手いこと行ってしまうのか不思議な気持ちが残り続けていました。最小全域木問題の最適性条件をハッキリと意識することによってようやく納得することができたので、そのことについて書いてみました。ここまで読んで頂いた方には感謝の気持ちで一杯です。
