最小全域木（最小スパニングツリー）とは：定義・性質・代表アルゴリズム
最小全域木（最小スパニングツリー）の定義・性質・代表アルゴリズム（Kruskal、Prim）を図解と例でわかりやすく解説。計算量や実装のポイントも紹介。
グラフ理論でよく扱われる問題の一つが、最小全域木（最小スパニング木、Minimum Spanning Tree; MST）です。グラフ理論での「木」とは、任意の2頂点間にちょうど1本の単純経路が存在するような連結グラフを指します。例えば、グラフが道路で結ばれた都市の集合を表すとき、すべての都市が互いに到達可能になるように道路（辺）を選ぶが、都市間の到達手段がちょうど1通りになるようにする選び方が「スパニング木」です。
同じグラフでも、道路の選び方（すなわちスパニング木）には複数の選択肢があり得ます。さらに、各辺にはコストや距離などの重みが付いていることが多く、これらの重みの合計が最小になるスパニング木を特に最小スパニング木（MST）と呼びます。
定義と基本事項
最小スパニング木は、次の条件を満たすものです。
- 元のグラフの全ての頂点を含む（スパニング）
- 閉路を含まず連結である（木である）
- その辺の重みの総和が可能な限り小さい（最小）
注意点：
- 元のグラフが非連結の場合には、各連結成分ごとに最小スパニング木を求めることになり、これらの集合は最小全域森（minimum spanning forest）と呼ばれます。
- すべての辺の重みが等しい場合、すべてのスパニング木がMSTになります。一方、すべての辺の重みが異なれば（重みの重複がない場合）、MSTは一意に定まります。
性質（重要な性質と証明の概略）
- カット性質（Cut property）：任意の頂点集合Sとその補集合の間にある辺のうち最小重みの辺は、あるMSTに必ず含まれる。直感的には、ある分割を越える最も安い架け橋は最適解の一部となるべき、という考え。
- サイクル性質（Cycle property）：任意のサイクルにおいて、最大重みの辺はあるMSTには含まれない。サイクルの中の最も高価な辺を取り除けば重みは下がるため。
- 最小ボトルネック木（Minimum Bottleneck Tree）との関係：MSTは必ず最小ボトルネック木でもある（最大辺重みを最小にする木）。ただし、逆は常に真ではない。
- 一意性：エッジ重みがすべて異なれば、MSTは一意。証明はカット性質を用いて簡単に示せます。
代表的なアルゴリズム
MSTを求める代表的なアルゴリズムには以下があります。いずれもグラフの辺に重みが付いた無向グラフを対象とします。
- Kruskalのアルゴリズム
すべての辺を重みの小さい順にソートし、順に取り出して既存の部分木に入れてもサイクルを作らないものだけを採用する方法。典型的にはUnion-Find（分解集合）を用いてサイクル判定を高速化します。
計算量（辺数をE、頂点数をVとすると）：ソートに O(E log E)（= O(E log V)） が支配的。Union-Findの実装でほぼこれが総コスト。
- Primのアルゴリズム
任意の始点から出発し、現在の木と接続する最小重みの辺を逐次追加していく貪欲法。優先度付きキュー（ヒープ）を使えば高速化できます。グラフが密（E ≈ V^2）な場合は隣接行列＋線形探索でも良い。
計算量：実装により O(E log V)（ヒープ使用）や O(V^2)（密グラフ）など。
- Borůvka（ボルヴカ）のアルゴリズム
各コンポーネントから接続する最小辺を同時に選んでマージしていく手法。並列化や分割統治に向く。複数回の反復で最終的にMSTを構築します。
計算量は実装に依存しますが、他の手法と組み合わせて効率化されることが多いです。
実装上のポイント
- Kruskalは辺が比較的少ない（スパース）グラフに向く。Union-Find（経路圧縮＋ランク併用）でほぼ定数時間に近い操作が可能。
- Primは連続した増加操作を行うため、頂点中心の構造を扱う場合に扱いやすい。二分ヒープやフィボナッチヒープを使うと理論上の計算量改善があるが、実装コストと実行時間のトレードオフを考慮する必要がある。
- グラフが非連結ならMSTではなく最小全域森（Minimum Spanning Forest）を返す。
- 辺の重みが負でもMSTの定義やアルゴリズムに支障はない（重みの大小比較だけを使う）。
- 有向グラフの場合はMSTの概念はそのままでは適用できない。最小有向全域木を求めるにはEdmondsのアルゴリズムなど別の手法が必要。
応用例
- 通信網や道路網などのコスト最小化によるネットワーク設計
- クラスタリング（データを木でつなぎ，適当な辺を切ることでクラスタ化）
- 近似アルゴリズム：TSP（巡回セールスマン問題）の近似解でMSTを利用する手法など
- 画像処理やセグメンテーションでの領域結合
まとめ（ポイント）
- 最小スパニング木は、全頂点を含む木のうち辺重み合計が最も小さいもの。
- 基本的性質としてカット性質・サイクル性質があり、これらを利用した貪欲法（Kruskal, Primなど）で効率的に構築できる。
- 辺重みがすべて異なればMSTは一意。非連結グラフでは最小全域森を考える。
- 実用的にはUnion-Findやヒープを用いた実装が高速で、ネットワーク設計やクラスタリングなど多くの分野で応用される。
平面グラフの最小スパニング木。各辺には重みが付けられており，ここでは長さにほぼ比例します．
最小スパニングツリーを見つける
初めての試み
最小スパニングツリーを発見するアルゴリズムを作るのは非常に簡単です。
関数 MST(G,W) .T = {} Tがスパニングツリーを形成していない間： Eの中でTに対して安全な最小の重み付き辺を求める T = T union {(u,v)} return Tこの場合、「安全」とは、その辺を含めてもグラフのサイクルが形成されないことを意味します。サイクルとは、ある頂点から始まり、他の多くの頂点まで移動し、同じ辺を二度使わずに再び始点で終わることを意味します。
歴史
チェコの科学者オタカル・ボルジュカは、1926年に木を最小化するアルゴリズムを開発しました。彼はモラヴィアの電気の効率的な範囲を見つける問題を解決したいと考えていました。今日、このアルゴリズムはボルジュフカのアルゴリズムとして知られています。他にも2つのアルゴリズムが一般的に使用されています。そのうちの1つは1930年にVojtěch Jarníkによって開発され、1957年にRobert Clay Primによって実用化されました。エドガー・ワイベ・ダイクストラが1959年に再発見し、プリムのアルゴリズムと呼ばれるようになりました。もう一つのアルゴリズムはクルスカルのアルゴリズムと呼ばれ、1956年にジョセフ・クルスカルによって提唱された。3つのアルゴリズムはすべて貪欲で、多項式時間で実行される。
今日までで最速の最小スパニングツリーアルゴリズムは、Bernard Chazelleによって開発されました。このアルゴリズムは、ソフトヒープ（近似優先度キュー）に基づいています。その実行時間はO(m α(m,n))であり、mは辺の数、nは頂点の数、αはアッカーマン関数の古典的な関数逆数です。関数αは非常にゆっくりと成長するので、実用的には4よりも大きくない定数と考えられます。
この問題のために可能な限り最速のアルゴリズムは何か？これはコンピュータサイエンスの中で最も古くからある未解決の問題の一つです。少なくともすべての重みを調べなければならないので、明らかに線形の下界があります。辺の重みがビット長が制限された整数であれば，線形の実行時間を持つ決定論的アルゴリズムが知られています．一般的な重みについては、期待される実行時間が線形であるランダム化アルゴリズムがあります。
この問題は分散的にアプローチすることもできます。各ノードをコンピュータとみなし、ノードが自分の接続されたリンク以外は何も知らない場合でも、分散型最小スパニングツリーを計算することができます。
質問と回答
Q: グラフ理論における最小スパニングツリーとは何ですか?
A:最小スパニングツリーとは、グラフ理論において、辺に付けられた重みの合計を最小にするツリーのことです。
Q: グラフ理論における木とは何ですか?
A:木とは、グラフ理論において、すべての頂点をつなぎ合わせる方法で、ある頂点から木の他の頂点への経路が1つだけとなるようにします。
Q: グラフ理論で都市を表現するシナリオで、道路を選択する目的は何ですか?
A: グラフ理論で都市を表現するシナリオで道路を選択する目的は、各都市が他のすべての都市から到達できるようにすることですが、ある都市から他の都市へ移動する可能性が1つ以上ないようにすることです。
Q: グラフは複数のスパニングツリーを持つことができますか?
A: はい、グラフは複数のスパニングツリーを持つことができます。
Q: 最小スパニングツリーと他のツリーの違いは何ですか?
A:最小スパニングツリーは、辺に付けられた重みの合計を最小化するもので、他のツリーにはこの機能はありません。
Q: グラフ理論におけるエッジとは何ですか?
A:エッジとは、グラフ理論における2つの頂点の間の接続のことです。
Q: グラフの最小スパニングツリーには、異なる重みを持つエッジが複数存在するのでしょうか?
A: はい，グラフの形状によっては，最小スパニングツリーは複数存在する可能性があります．
百科事典を検索する