クラスカル法

クラスカル法は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。

1. 概要
-----

このアルゴリズムは、1956年にジョゼフ・クラスカルが //Proceedings of the American Mathematical Society// で発表した 。

クラスカル法は貪欲法の一種で、最小全域木を求める他のアルゴリズムとしては、プリム法、逆削除法、ブルーフカ法などがある。最小全域木とは、グラフの全ての頂点を含む木で、辺の重みの総和が最小のものを言う。連結されていないグラフでは、「最小全域森」を求められる。

2. アルゴリズムの解説
------------

クラスカル法の手順は次の通り。

グラフの各頂点がそれぞれの木に属するように、森 //F// を生成する//S// ← グラフの全ての辺を含む集合 while //S// から重みが最小の辺 //e// を削除する if //e// を森に加え、2つの木を1つにまとめる

このアルゴリズムが終了した時点で、森は単一の木となっており、元のグラフの最小全域木になっている。

3. 性能
-----

グラフ内の辺数を //E//、頂点数を //V// とすると、クラスカル法の計算量はデータ構造が単純であれば //O// または //O// である。これらは次の理由で等価である。

//E// は最大でも //V//2 であり、log //V//2 = 2 log //V// であるから log //E// は //O// である。
孤立した頂点はそれ自体が必ず最小全域木となるので無視すると、//V// ≤ //E//+1 であるから log //V// は //O// である。この計算量は以下のように求められる。まず、辺を重みでソートするのに比較ソートを用いると //O// となる。これにより、「//S// から重みが最小の辺を削除する」操作を定数時間で行えるようになる。次にどの頂点がどの木に属しているかを保持するのに素集合データ構造を使う。各辺について、2回の探索操作と1回の和集合操作が必要であり、O 回となる。単純な素集合データ構造であっても //O// の時間内に O 回の操作を実行できる。したがって、総計算量は //O// = //O// である。

辺が事前にソート済みか線形時間でソートできる場合、より洗練された素集合データ構造を使うことができ、//O//) の計算量になる。ここでαはアッカーマン関数の逆関数で極めてゆっくり増加する。

4. 例
----



5. 正しさの証明
---------

このアルゴリズムの正しさの証明は2つの部分に分けられる。第一は全域木を生成していること、第二はそれが最小の重みであることである。

5.1. 全域木
--------

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

5.2. 最小性
--------

この証明には背理法を用いる。 が最小全域木でないとすると、別に最小全域木が一つ以上存在する。それらの中から、 と共通する辺の数が最も多い木 を選ぶ。 に含まれ には含まれない辺の中で、本アルゴリズムによって に最初に追加される 辺 について考える。

には閉路が存在する。 は木であるので、閉路を形成する辺を全部含むことはない。したがって、この閉路には には含まれない辺 //f// が存在する。 も全域木であるから、その重みは より小さいはずがなく、//e// の重みは //f// より小さいはずがない。ここで別の背理法を用いて //f// の重みが //e// より小さいはずがないことを証明する。 に追加する辺は常に重みの小さいほうから選んでいた。したがって、 仮に //f// の重みが //e// より小さいとすると、//f// は //e// より以前に検討されたはずで、 部分森 への追加をするか調べたはずである。しかし //f// は で閉路を形成していないので、 においても閉路を形成しないはずであり、木に追加されていたはずである。これは、 //f// が に含まれない辺であるということに反する。よって、//f// の重みは //e// より小さいことはない。

以上により、 //e// と //f// は同じ重みであることが示される。したがって も最小全域木である。しかし は よりも と共通する辺が1つ多い。これは の定義と矛盾する。

6. 擬似コード
--------

1 function Kruskal 2 for each vertex //v// in //G// do 3 Define an elementary cluster //C// ← {//v//}. 4 Initialize a priority queue //Q// to contain all edges in //G//, using the weights as keys. 5 Define a tree //T// ← Ø ////T// は最終的に最小全域木の辺を含む。 6 // n は全頂点数 7 while //T// has fewer than //n//-1 edges do 8 // 辺 u,v は v にとって重みが最小の経路である。 9  ← //Q//.removeMin 10 // T に閉路が含まれないようにする。T に既に u と v を結ぶ経路がない場合のみ u,v を追加する。 11 // つまり、u と v が違うクラスターに属する場合のみ u,v を追加する。 13 Let //C// be the cluster containing //v//, and let //C// be the cluster containing //u//. 14 if //C// ≠ //C// then 15 Add edge  to //T//. 16 Merge //C// and //C// into one cluster, that is, union //C// and //C//. 17 return tree //T//

7. 関連項目
-------

プリム法
ブルーフカ法
ダイクストラ法
ツォルンの補題

8. 参考文献
-------

Joseph. B. Kruskal: //[1]//. In: //Proceedings of the American Mathematical Society//, Vol 7, No. 1 , pp. 48–50
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. //Introduction to Algorithms//, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
Michael T. Goodrich and Roberto Tamassia. //Data Structures and Algorithms in Java//, Fourth Edition. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0. Section 13.7.1: Kruskal's Algorithm, pp.632.

9. 外部リンク
--------

[2]
[3] at cut-the-knot
[4]