ボルフカのアルゴリズム

ボルフカのアルゴリズムは、グラフにおける最小全域木、または連結していないグラフの場合は最小全域森を見つけるための貪欲アルゴリズムである。

これは、1926年にオタカール・ボルーフカによってモラヴィアの効率的な電力ネットワークを構築する方法として初めて発表されました。^[¹^]^[²^]^[³^]このアルゴリズムは、1938年にショケによって再発見され、 ^[⁴^] 1951年にはフロレク、ウカシェヴィチ、ペルカル、シュタインハウス、ズブジツキによって再び発見され、^[⁵^] 1965年にはジョルジュ・ソリンによって再び発見されました。 ^[⁶^]このアルゴリズムは、特に並列コンピューティングの文献では、ソリンのアルゴリズムと呼ばれることがよくあります。

このアルゴリズムは、まずグラフの各頂点に接続する最小重みの辺を見つけ、それらの辺すべてをフォレストに追加します。次に、これまでに構築された各木から別の木への最小重みの辺を見つけ、それらの辺すべてをフォレストに追加するという同様のプロセスを繰り返します。このプロセスを繰り返すたびに、グラフの各連結成分内の木の数は、以前の値の半分以下に減少するため、対数的に多くの繰り返しの後、プロセスは終了します。プロセスが終了すると、追加された辺の集合が最小全域フォレストを形成します。

擬似コード

以下の擬似コードは、ボルーフカのアルゴリズムの基本的な実装例を示しています。条件節では、すべてのエッジuvは「なし」よりも安価であるとみなされます。completed変数の目的は、フォレストFがまだ全域フォレストであるかどうかを判断することです。

エッジに異なる重みがない場合は、頂点またはエッジの全順序などに基づく一貫したタイブレーク規則を使用する必要があります。これは、頂点を整数として表現して直接比較したり、メモリアドレスを比較したりすることで実現できます。タイブレーク規則は、作成されたグラフが実際に森であり、サイクルを含まないことを保証するために必要です。たとえば、ノード { a、b、c } とすべてのエッジの重みが 1 である三角形グラフを考えます。この場合、{ a } の最小重みエッジとしてab、{ b } の最小重みエッジとしてbc、{ c } の最小重みエッジとしてca を選択すると、サイクルが作成される可能性があります。エッジを最初にソース、次に宛先で順序付けるタイブレーク規則を使用すると、サイクルの作成が防止され、最小全域木 { ab、bc } が得られます。

アルゴリズムBorůvkaは、入力:重み付き無向グラフG = ( V , E )です 。 出力: Gの最小全域森Fです。 森F を( V , E ′ ) に初期化します。ここでE ′ = {} です。 completed := false while not completed do Fの連結成分 を見つけ、各頂点にその成分を割り当てる 各コンポーネントの最も安価なエッジを「なし」に初期化します。 Eの各辺uvについて、uとvはFの異なる成分に属する。wx を uの コンポーネントの最安エッジとする。is -preferred-over( uv , wx )の場合、uv をuのコンポーネントの最安エッジとする 。yzをvのコンポーネントの最安エッジとする 。is -preferred-over( uv , yz )の場合、uv をvのコンポーネントの最安エッジと する。すべてのコンポーネントの最安エッジが "None" に設定されている場合、 //これ以上ツリーをマージすることはできない -- 処理が完了した。completed : = trueそれ以外の場合はcompleted := false最安エッジが "None" でない各コンポーネントについて、 その最安エッジをE'に追加する。関数is-preferred-over( edge1 , edge2 )は ( edge2が "None")を返します。 (weight( edge1 ) < weight( edge2 )) または (weight( edge1 ) = weight( edge2 ) かつ tie-breaking-rule( edge1 , edge2 )) function tie-breaking-rule( edge1 , edge2 ) is タイブレークルール。同点の場合にedge1 がedge2 より優先される場合にのみtrueを返します。

最適化として、同じコンポーネント内の2つの頂点を結ぶことが判明した各エッジをGから削除することで、後のコンポーネントで最も安いエッジを探索する時間に影響を与えないようにすることができる。

複雑

ボルーヴカのアルゴリズムは、外側のループが終了するまでに $O (log V)$ 回繰り返すことが示されており、したがって、実行時間は $O (E log V)$ となります。ここで、 $E$ はエッジの数、 $Vは$ $G$ の頂点の数です( $E \geq V$ と仮定)。平面グラフ、より一般的にはグラフマイナー操作で閉じられるグラフの族では、アルゴリズムの各段階の後、各コンポーネントのペア間の最も安いエッジ以外のすべてのエッジを削除することで、線形時間で実行できます。^{[ 7 ]}

例

その他のアルゴリズム

この問題に対する他のアルゴリズムとしては、プリムのアルゴリズムとクラスカルのアルゴリズムがある。プリムのアルゴリズムとボルーフカのアルゴリズムを組み合わせることで、高速な並列アルゴリズムが得られる。^{[ 8 ]}

カルガー、クライン、タージャンによる、ボルフカのアルゴリズムを部分的にベースとした、より高速なランダム化最小全域木アルゴリズムは、期待値 $O(E)$ 時間で実行されます。^{[ 9 ]}ベルナール・シャゼルによる最もよく知られている（決定論的な）最小全域木アルゴリズムも、ボルフカのアルゴリズムを部分的にベースとしており、 $O(Eα (E, V))$ 時間で実行されます。ここで、αは逆アッカーマン関数です。^{[ 10 ]}これらのランダム化アルゴリズムと決定論的アルゴリズムは、ボルフカのアルゴリズムのステップ（接続されていないコンポーネントの数を減らす）と、コンポーネントのペア間のエッジの数を減らす別のタイプのステップを組み合わせています。

注記

↑オタカルのボルフカ(1926 年)。"O jistém problému minimálním" [ある最小限の問題について]。モルをプレースプルシーロドヴェド。スポル。 V ブルネ III (チェコ語とドイツ語)。3：37～ 58。
↑オタカルのボルフカ(1926 年)。「Příspěvek k šešení otázky ekonomické stavby elektrovodních sítí (電力網の経済的な構築の問題の解決への貢献)」。Elektronický Obzor (チェコ語)。15 : 153–154 .
↑ネシェツィル、ヤロスラフ;ミルコバ、エヴァ。ネシェトジロヴァ、ヘレナ (2001)。「最小スパニングツリー問題に関するOtakar Borůvka: 1926年の両方の論文の翻訳、コメント、歴史」。離散数学。233 ( 1–3 ): 3–36 .土井: 10.1016/S0012-365X(00)00224-7。hdl : 10338.dmlcz/500413。MR 1825599。
↑ギュスターヴ・ショケ（1938年）。「あるルートの研究」。Comptes Rendus de l'Académie des Sciences (フランス語)。206 : 310 – 313.
↑フロレク、K。ウカシェヴィチ、J. ;パーカル、J.ヒューゴ・シュタインハウス;ズブジツキ、S. (1951)。「最終的なアンサンブルの連絡と点の分割」。Colloquium Mathematicum (フランス語)。2 ( 3–4 ): 282–285 .ドイ: 10.4064/cm-2-3-4-282-285。MR 0048832。
↑ジョルジュ・ソラン (1965)。「運河の跡」。プログラミング、ゲーム、交通ネットワーク(フランス語)。
↑ Eppstein, David (1999). "Spanning trees and spanners". Sack, J.-R. ; Urrutia, J. (eds.). Handbook of Computational Geometry . Elsevier. pp. 425–461 . ;マレシュ、マルティン (2004)。「マイナー閉グラフクラスにおける MST の 2 つの線形時間アルゴリズム」(PDF)。数学のアーカイブ。40 (3): 315–320 .。
↑ Bader, David A.; Cong, Guojing (2006). "疎グラフの最小全域フォレストを計算するための高速共有メモリアルゴリズム". Journal of Parallel and Distributed Computing . 66 (11): 1366–1378 . CiteSeerX 10.1.1.129.8991 . doi : 10.1016/j.jpdc.2006.06.001 . S2CID 2004627 .
↑ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "最小全域木を見つけるためのランダム化線形時間アルゴリズム". Journal of the ACM . 42 (2): 321– 328. CiteSeerX 10.1.1.39.9012 . doi : 10.1145/201019.201022 . S2CID 832583 .
↑ Chazelle, Bernard (2000). "逆アッカーマン型複雑度を持つ最小全域木アルゴリズム" (PDF) . J. ACM . 47 (6): 1028– 1047. CiteSeerX 10.1.1.115.2318 . doi : 10.1145/355541.355562 . S2CID 6276962 .

[1] オタカルのボルフカ(1926 年)。"O jistém problému minimálním" [ある最小限の問題について]。モルをプレースプルシーロドヴェド。スポル。 V ブルネ III (チェコ語とドイツ語)。3：37～ 58。

[2] オタカルのボルフカ(1926 年)。「Příspěvek k šešení otázky ekonomické stavby elektrovodních sítí (電力網の経済的な構築の問題の解決への貢献)」。Elektronický Obzor (チェコ語)。15 : 153–154 .

[3] ネシェツィル、ヤロスラフ;ミルコバ、エヴァ。ネシェトジロヴァ、ヘレナ (2001)。「最小スパニングツリー問題に関するOtakar Borůvka: 1926年の両方の論文の翻訳、コメント、歴史」。離散数学。233 ( 1–3 ): 3–36 .土井: 10.1016/S0012-365X(00)00224-7。hdl : 10338.dmlcz/500413。MR 1825599。

[4] ギュスターヴ・ショケ（1938年）。「あるルートの研究」。Comptes Rendus de l'Académie des Sciences (フランス語)。206 : 310 – 313.

[5] フロレク、K。ウカシェヴィチ、J. ;パーカル、J.ヒューゴ・シュタインハウス;ズブジツキ、S. (1951)。「最終的なアンサンブルの連絡と点の分割」。Colloquium Mathematicum (フランス語)。2 ( 3–4 ): 282–285 .ドイ: 10.4064/cm-2-3-4-282-285。MR 0048832。

[6] ジョルジュ・ソラン (1965)。「運河の跡」。プログラミング、ゲーム、交通ネットワーク(フランス語)。

[7] Eppstein, David (1999). "Spanning trees and spanners". Sack, J.-R. ; Urrutia, J. (eds.). Handbook of Computational Geometry . Elsevier. pp. 425–461 . ;マレシュ、マルティン (2004)。「マイナー閉グラフクラスにおける MST の 2 つの線形時間アルゴリズム」(PDF)。数学のアーカイブ。40 (3): 315–320 .。

[8] Bader, David A.; Cong, Guojing (2006). "疎グラフの最小全域フォレストを計算するための高速共有メモリアルゴリズム". Journal of Parallel and Distributed Computing . 66 (11): 1366–1378 . CiteSeerX 10.1.1.129.8991 . doi : 10.1016/j.jpdc.2006.06.001 . S2CID 2004627 .

[9] Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "最小全域木を見つけるためのランダム化線形時間アルゴリズム". Journal of the ACM . 42 (2): 321– 328. CiteSeerX 10.1.1.39.9012 . doi : 10.1145/201019.201022 . S2CID 832583 .

[10] Chazelle, Bernard (2000). "逆アッカーマン型複雑度を持つ最小全域木アルゴリズム" (PDF) . J. ACM . 47 (6): 1028– 1047. CiteSeerX 10.1.1.115.2318 . doi : 10.1145/355541.355562 . S2CID 6276962 .

[

[

[

[

[

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

擬似コード

複雑

例

その他のアルゴリズム

注記

関連するトピック

最小全域木

貪欲アルゴリズム

これは、1926年にオタカール・ボルーフカによって

モラヴィア