ブルーフカ法

ブルーフカ法（ブルーフカほう、英: Borůvka's algorithm）とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。

概要

このアルゴリズムは1926年に、チェコの数学者オタカル・ボルフカがモラヴィアでの電力網を敷く際に発見した^[1]^[2]^[3]。またその後、ギュスターヴ・ショケ（英語版）（1938）^[4]・ウカシェヴィチら（1951）^[5]・ソリン（1965）^[6] がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に並列計算の分野ではソリンアルゴリズムとも呼ばれる。

アルゴリズムの解説

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

例

イメージ	木・森	説明
	{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)かかる。平面グラフでは、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。

その他のアルゴリズムとの比較

クラスカル法はブルーフカ法と同じく、アルゴリズム開始時に全ての頂点でノード一つの木を作成する。それに対して、プリム法では木を最初に決定したひとつの頂点から拡大していく。

知られている最小全域木を求める最適化問題のアルゴリズムの中でもっとも効率の良いバーナード・チャゼル（英語版）のアルゴリズムは O(E α(E,V)) の計算量で、ブルーフカ法を参考にしている。

出典

[脚注の使い方]

^ Borůvka, Otakar (1926). “O jistém problému minimálním [About a certain minimal problem]” (cs, de). Práce Mor. Přírodověd. Spol. V Brně III 3: 37–58. https://dml.cz/handle/10338.dmlcz/500114.
^ Borůvka, Otakar (1926). “Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)” (チェコ語). Elektronický Obzor 15: 153–154.
^ Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). “Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history”. Discrete Mathematics 233 (1–3): 3–36. doi:10.1016/S0012-365X(00)00224-7. hdl:10338.dmlcz/500413. MR1825599.
^ Choquet, Gustave (1938). “Étude de certains réseaux de routes” (フランス語). Comptes Rendus de l'Académie des Sciences 206: 310–313.
^ Florek, K.; Łukaszewicz, J.; Perkal, J.; Steinhaus, Hugo; Zubrzycki, S. (1951). “Sur la liaison et la division des points d'un ensemble fini” (フランス語). Colloquium Mathematicae 2 (3–4): 282–285. doi:10.4064/cm-2-3-4-282-285. MR0048832. https://eudml.org/doc/209969.
^ Sollin, Georges (1965). “Le tracé de canalisation” (フランス語). Programming, Games, and Transportation Networks.

参考文献

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

数理最適化 • 最適化問題 : メソッド • ヒューリスティック

非線形(無制約)

… 関数　

黄金分割探索
直線探索
ネルダー–ミード法
連続放物線補間（英語版）

勾配法

収束性	信頼領域ウルフ条件（英語版）
準ニュートン法	BFGS法ブロイデン法 L-BFGS（英語版） DFP法対称ランク1法（英語版）
その他の求解法	ガウス・ニュートン法最急降下法レーベンバーグ・マルカート法共役勾配法（非線形共役勾配法）切り捨てニュートン法（英語版）ドッグレッグ法

… ヘッセ行列

最適化におけるニュートン法（英語版）

非線形(制約付き)

一般	バリア関数ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法逐次二次計画法連続線形計画（英語版）

凸最適化

凸縮小化

切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
簡約勾配法
劣勾配法（英語版）

線型および
二次

内点法	カチヤンの楕円体法カーマーカーの投影アルゴリズム
ベイズ-交換	単体法改訂単体法（英語版）十文字法（英語版）レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例
(Paradigms)

グラフ理論

最小全域木	ベルマン–フォード法ブルーフカ法ダイクストラ法ワーシャル–フロイド法ジョンソン法（英語版）クラスカル法
最大フロー問題	Dinic法（英語版）エドモンズ・カープフォード・ファルカーソンプッシュリラベル最大流アルゴリズム（英語版）