ブルーフカ法

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

概要 
このアルゴリズムは1926年に、チェコの数学者 がモラヴィアでの電力網を敷く際に発見した。またその後、（1938）・ウカシェヴィチら（1951）・ソリン（1965） がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に並列計算の分野ではソリンアルゴリズムとも呼ばれる。

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

例

計算量 
辺の数を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

エポニム
全域木