ブルーフカ法

ブルーフカ法 ブルーフカ法は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 目次 1 概要 2 アルゴリズムの解説 3 例 4 計算量 5 その他のアルゴリズムとの比較 6 参考文献 概要[編集] このアルゴリズムは1926年に、数学者オタカール・ブルーフカがモラヴィアでの電力網を敷く際に発見した。またその後、ショケット(1938)・ウカシェヴィチら(1951)・ソリン (1965) がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に並列計算の分野では別名ソリンアルゴリズムとも呼ばれる。

アルゴリズムの解説[編集] このアルゴリズムではまず、頂点ひとつの木を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森（木の集合）に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。

例[編集] 画像 木 説明

{A} {B} {C} {D} {E} {F} {G} アルゴリズム適用前のグラフでは、木を表す青い丸は、ノードひとつひとつについている。辺付近の数字は重みを表す。

{A,B,D,F} {C,E,G} アルゴリズムの反復の１回目では木の最小の重みの辺を選ぶ。辺AD, 辺CEはそれぞれ２回ずつ選択されている。グラフ全体では森がまだ２つ残っている。

{A,B,C,D,E,F,G} アルゴリズムの反復の２回目ではそれぞれの森から、他の森に繋がる最小の重みの辺であるを辺BE選択する。木が一つになったためアルゴリズムは終了。

計算量[編集]

辺の数をE、Vを頂点の数として、ブルーフカ法は O(log V)回の反復をするため、計算には時間 O(E log V)かかる。平面グラフでは、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。 その他のアルゴリズムとの比較[編集] クラスカル法はブルーフカ法と同じく、アルゴリズム開始時に全ての頂点でノード一つの木を作成する。それに対して、プリム法では木を最初に決定したひとつの頂点から拡大していく。 知られている最小全域木を求める最適化問題のアルゴリズムの中でもっとも効率の良いBernard ChazelleのアルゴリズムはO(E α(E,V))の計算量で、ブルーフカ法を参考にしている。 参考文献[編集] Nešetřil, Jaroslav, Eva Milková, and Helena Nešetřilová. "Otakar Borůvka on minimum spanning tree problem translation of both the 1926 papers, comments, history." Discrete mathematics 233.1-3 (2001): 3-36. http://www.cs.mun.ca/~kol/courses/6901-f16/boruvka-nmn.pdf