「ブルーフカ法」の版間の差分
編集の要約なし |
Wikipedia内リンクを1点修正: 「連結」→「連結グラフ」。Wikipedia内リンクを3点追加: 「重み」「ノード」「線形」。 |
||
1行目: | 1行目: | ||
{{著作権問題調査依頼}} |
{{著作権問題調査依頼}} |
||
{{Wikify|date=2017年8月1日 (火) 10:25 (UTC)}} |
{{Wikify|date=2017年8月1日 (火) 10:25 (UTC)}} |
||
'''ブルーフカ法'''とは、[[グラフ理論]]で重み付き[[連結グラフ |
'''ブルーフカ法'''とは、[[グラフ理論]]で[[ウェイト (表現論)|重み]]付き[[連結グラフ]]の最小[[全域木]]を求める[[最適化問題]]の[[アルゴリズム]]である。 |
||
== 概要 == |
== 概要 == |
||
7行目: | 7行目: | ||
== アルゴリズムの解説 == |
== アルゴリズムの解説 == |
||
このアルゴリズムではまず、頂点ひとつの[[木 (数学)|木]]を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。 |
このアルゴリズムではまず、頂点ひとつの[[木 (数学)|木]]を全ての[[頂点 (グラフ理論)|ノード]]について作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。 |
||
== 例 == |
== 例 == |
||
31行目: | 31行目: | ||
== 計算量 == |
== 計算量 == |
||
辺の数をE、Vを頂点の数として、ブルーフカ法は{{math|''O''(log ''V'')}}回の反復をするため、計算には時間{{math|''O''(''E'' log ''V'')}}かかる。[[平面グラフ]]では、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。 |
辺の数をE、Vを頂点の数として、ブルーフカ法は{{math|''O''(log ''V'')}}回の反復をするため、計算には時間{{math|''O''(''E'' log ''V'')}}かかる。[[平面グラフ]]では、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より[[線型性|線形]]に近い計算量で済む。 |
||
== その他のアルゴリズムとの比較 == |
== その他のアルゴリズムとの比較 == |
2021年9月29日 (水) 23:24時点における版
このページは著作権侵害のおそれが指摘されており、事実関係の調査が依頼されています。
このページの現在または過去の版は、ウェブサイトや書籍などの著作物からの無断転載を含んでいるおそれが指摘されています。もしあなたが転載元などをご存知なら、どうぞこのページのノートまでご一報ください。 著作権侵害が確認されると、このページは削除の方針により一部の版または全体が削除されます。もしこのページの加筆や二次利用をお考えでしたら、この点を十分にご認識ください。 |
ブルーフカ法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。
概要
このアルゴリズムは1926年に、チェコの数学者オタカール・ブルーフカ がモラヴィアでの電力網を敷く際に発見した。またその後、ショケット (1938)・ウカシェヴィチら(1951)・ソリン (1965) がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に並列計算の分野ではソリンアルゴリズムとも呼ばれる。
アルゴリズムの解説
このアルゴリズムではまず、頂点ひとつの木を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。
例
計算量
辺の数をE、Vを頂点の数として、ブルーフカ法はO(log V)回の反復をするため、計算には時間O(E 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