ブルーフカ法

ブルーフカ法（ブルーフカほう、英: 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.
^ 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

[1] 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.

[2] 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.

[3] 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.

[4] Choquet, Gustave (1938). “Étude de certains réseaux de routes” (フランス語). Comptes Rendus de l'Académie des Sciences 206: 310–313.

[5] 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.

[6] Sollin, Georges (1965). “Le tracé de canalisation” (フランス語). Programming, Games, and Transportation Networks.

[1]

[2]

[3]

[4]

[5]

[6]