グラフ理論でよく扱われる問題の一つが、最小全域木（最小スパニング木、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やヒープを用いた実装が高速で、ネットワーク設計やクラスタリングなど多くの分野で応用される。