「ブルーフカ法」の版間の差分

マークアップ
m (Wikify|data=)
(マークアップ)
{{著作権問題調査依頼}}
{{Wikify|date=2017年8月1日 (火) 10:25 (UTC)}}
'''ブルーフカ法 '''({{lang-en-short|Kruskal's algorithm}})とは、[[グラフ理論において]]で重み付き[[連結グラフ|連結]]グラフの最小[[全域木]]を求める[[最適化問題]][[アルゴリズム]]である。
ブルーフカ法
ブルーフカ法は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。
目次
1 概要
2 アルゴリズムの解説
3 例
4 計算量
5 その他のアルゴリズムとの比較
6 参考文献
概要[編集]
このアルゴリズムは1926年に、数学者オタカール・ブルーフカがモラヴィアでの電力網を敷く際に発見した。またその後、ショケット(1938)・ウカシェヴィチら(1951)・ソリン (1965) がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に並列計算の分野では別名ソリンアルゴリズムとも呼ばれる。
 
1== 概要 ==
アルゴリズムの解説[編集]
このアルゴリズムは[[1926年]]に、数学者 {{仮リンク|オタカール・ブルーフカ|en|Otakar Borůvka}} [[モラヴィア]]での電力網を敷く際に発見した。またその後、{{仮リンク|ショケット|en|Gustave Choquet}} (1938)・[[ウカシェヴィチ]]ら(1951)・ソリン (1965) がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に[[並列計算]]の分野では別名ソリンアルゴリズムとも呼ばれる。
このアルゴリズムではまず、頂点ひとつの木を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。
 
2== アルゴリズムの解説 ==
このアルゴリズムではまず、頂点ひとつの[[ (数学)|木]]を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。
 
== [編集] ==
画像
説明
 
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
{A}
! | イメージ
{B}
! width="100" | 木・森
{C}
! | 説明
{D}
|-
{E}
|[[File:Borůvka Algorithm 1.svg|200px]]
{F}
| {A}<br/>{B}<br/>{C}<br/>{D}<br/>{E}<br/>{F}<br/>{G}
{G}
|アルゴリズム適用前のグラフでは、木を表す青い丸は、ノードひとつひとつについている。辺付近の数字は重みを表す。
|-
|[[File:Borůvka Algorithm 2.svg|200px]]
| {A,B,C,D,E,F}<br/>{C,E,G}
|アルゴリズムの反復の1回目では木の最小の重みの辺を選ぶ。辺AD, 辺CEはそれぞれ2回ずつ選択されている。グラフ全体では森がまだ2つ残っている。
|-
|[[File:Borůvka Algorithm 3.svg|200px]]
| {A,B,C,D,E,F,G}
|アルゴリズムの反復の2回目ではそれぞれの森から、他の森に繋がる最小の重みの辺であるを辺BE選択する。木が一つになったためアルゴリズムは終了。
|}
 
{A,B,D,F}
{C,E,G}
アルゴリズムの反復の1回目では木の最小の重みの辺を選ぶ。辺AD, 辺CEはそれぞれ2回ずつ選択されている。グラフ全体では森がまだ2つ残っている。
 
4== 計算量 ==
{A,B,C,D,E,F,G}
辺の数をE、Vを頂点の数として、ブルーフカ法は[[Big O notation|O]](log ''V'')回の反復をするため、計算には時間[[Big O notation|O]](''E'' log ''V'')かかる。[[平面グラフ]]では、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。
アルゴリズムの反復の2回目ではそれぞれの森から、他の森に繋がる最小の重みの辺であるを辺BE選択する。木が一つになったためアルゴリズムは終了。
計算量[編集]
 
5== その他のアルゴリズムとの比較 ==
辺の数をE、Vを頂点の数として、ブルーフカ法は O(log V)回の反復をするため、計算には時間 O(E log V)かかる。平面グラフでは、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。
[[クラスカル法]]はブルーフカ法と同じく、アルゴリズム開始時に全ての頂点でノード一つの木を作成する。それに対して、[[プリム法]]では木を最初に決定したひとつの頂点から拡大していく。
その他のアルゴリズムとの比較[編集]
知られている最小全域木を求める最適化問題のアルゴリズムの中でもっとも効率の良い {{仮リンク|バーナード・チャゼル|en|Bernard Chazelle}} のアルゴリズムは {{math|O(''E'' α(''E'',''V''))}} の計算量で、ブルーフカ法を参考にしている。
クラスカル法はブルーフカ法と同じく、アルゴリズム開始時に全ての頂点でノード一つの木を作成する。それに対して、プリム法では木を最初に決定したひとつの頂点から拡大していく。
 
知られている最小全域木を求める最適化問題のアルゴリズムの中でもっとも効率の良いBernard Chazelleのアルゴリズムは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
* [[クラスカル法]]
 
6== 参考文献 ==
* 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
5

回編集