ブルーフカ法

ブルーフカ法（Borůvka's algorithm）

概要

ブルーフカ法は、グラフ理論において、重み付き連結グラフの最小全域木を求めるためのアルゴリズムです。最小全域木とは、グラフ内の全ての頂点を連結し、辺の重みの合計が最小となる木構造のことです。

このアルゴリズムは、1926年にチェコの数学者オタカル・ブルーフカによって、モラヴィア地方の電力網を敷設する際に考案されました。その後、ギュスターヴ・ショケ（1938年）、ウカシェヴィチら（1951年）、ソリン（1965年）によっても独立に再発見されています。特に並列計算の分野では、ソリンアルゴリズムとも呼ばれることがあります。

アルゴリズムの詳細

1. 初期化: グラフ内の各頂点をそれぞれ独立した木（一つの頂点のみからなる木）として扱います。この時点では、グラフは複数の木（森）の集合として表現されます。
2. 最小重み辺の選択: 各木に対して、その木と他の木を繋ぐ辺のうち、重みが最小の辺を一つ選択します。この際、複数の木が同じ辺を選ぶこともあります。これは複数の木が連結されることを意味します。
3. 木の連結: 選択された辺を用いて木同士を連結します。これにより、森を構成する木の数が減少します。
4. 繰り返し: 全ての木が一つに連結されるまで、ステップ2と3を繰り返します。最終的に得られた木が最小全域木となります。

具体例

具体的な例を用いて、ブルーフカ法の動作を説明します。

[ここに具体的なグラフとアルゴリズムのステップごとの状態遷移の図解があると、より理解が深まる]

計算量

ブルーフカ法の計算量は、グラフの頂点数をV、辺数をEとした場合に、O(E log V)となります。これは、アルゴリズムが最大でO(log V)回の反復を行うためです。平面グラフの場合、反復ごとに不要な辺を取り除くことで、より線形に近い計算量で済む場合があります。

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

ブルーフカ法は、最小全域木を求める他のアルゴリズムと比較して、以下の特徴を持ちます。

クラスカル法: ブルーフカ法と同様に、初期状態で各頂点を独立した木として扱います。両者とも、森を徐々に連結していくアプローチを採用しています。
プリム法: プリム法では、特定の開始頂点から木を徐々に拡大していく点が異なります。これは、ブルーフカ法が複数の木を同時に連結していくアプローチとは対照的です。
バーナード・チャゼルのアルゴリズム: 最小全域木を求めるアルゴリズムの中で、最も効率的であるとされるバーナード・チャゼルのアルゴリズム（計算量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


この参考文献は、ブルーフカ法に関するオリジナルの論文を翻訳したものであり、歴史的な背景や詳細な解説が含まれています。

もう一度検索