2-3 最小全域木
最安のnetworkは局所的選択で作れるか
都市を頂点、建設可能な回線を辺、費用を辺重みとします。全都市を通信可能にしたい一方、cycle上の一本は連結性だけを目的にするなら冗長です。従って最安networkはspanning treeの中から探せばよいことになります。
しかし、目についた最軽量辺を順に選ぶだけで、本当に全体の費用が最小になるでしょうか。一般の最適化問題では、局所的に最良な選択が大域的最適解を壊すことがあります。本章では、spanning treeの交換法則があるためにgreedy選択が安全であることを証明します。
重み付きグラフと最小全域木
有限グラフ $G=(V,E)$ の各辺 $e$ に実数 $w(e)$ を対応させたものを重み付きグラフ|weighted graphという。辺集合 $F\subseteq E$ の重みを
$$
w(F)=\sum_{e\in F}w(e)
$$
と定める。
$G$ が連結であるとき、$G$ のspanning treeのうち重みが最小のものを最小全域木|minimum spanning tree、略してMSTという。
重みは負でも構いません。どのspanning treeも辺数が $|V|-1$ であり、候補は有限個なので最小値は必ず達成されます。
有限連結weighted graphは少なくとも一つMSTをもつ。
有限グラフの辺部分集合は有限個しかないので、spanning treeも有限個です。連結性により少なくとも一つspanning treeが存在します。従ってspanning treeの重みからなる空でない有限実数集合は最小値をもち、その値を取る木がMSTです。□
cutを横切る軽い辺は安全である
頂点集合の非自明な分割 $V=S\sqcup(V\setminus S)$ を考えます。この二側を結ぶには、どのspanning treeもcut $\delta(S)$ の辺を少なくとも一本使わなければなりません。
有限連結weighted graph $G$ のcut $\delta(S)$ において、重みが最小の辺を $e$ とする。このとき $e$ を含むMSTが存在する。
さらに $e$ がこのcut上で一意な最軽量辺なら、すべてのMSTが $e$ を含む。
まずMST $T$ を一つ取ります。$e\in T$ なら前半は終わりです。$e\notin T$ とします。$T+e$ には「全域木と切断・閉路の性質」のfundamental cycle $C_T(e)$ がただ一つできます。$e$ はcutの一方から他方へ渡るので、このcycleは元の側へ戻るために、$e$ 以外にもcutを横切る辺 $f$ を含みます。
$e$ はcut上の最軽量辺なので $w(e)\le w(f)$ です。cycle交換定理により
$$
T'=T+e-f
$$
はspanning treeで、
$$
w(T')=w(T)+w(e)-w(f)\le w(T).
$$
$T$ はMSTなのでこれより軽いspanning treeはなく、等号が成り立って $T'$ もMSTです。しかも $e\in T'$ です。
次に $e$ が一意な最軽量辺とします。$e$ を含まないMST $T$ があったと仮定すると、上と同じ $f$ に対して $w(e)< w(f)$ です。従って $w(T')< w(T)$ となり、$T$ の最小性に反します。ゆえにすべてのMSTが $e$ を含みます。□
「最軽量辺を必ず含む」ではなく、同率がある場合は「それを含むMSTが少なくとも一つある」です。この量化の違いが重要です。
cycle上の重い辺は捨てられる
cut propertyの双対がcycle propertyです。
有限連結weighted graph $G$ のcycle $C$ 上で重み最大の辺を $e$ とする。このとき $e$ を含まないMSTが存在する。
さらに $e$ が $C$ 上で一意な最重量辺なら、どのMSTも $e$ を含まない。
まずMST $T$ を一つ取ります。$e\notin T$ なら前半は終わりです。$e\in T$ とします。$T-e$ は二成分に分かれます。cycle $C$ から $e$ を除いた残りは $e$ の両端を結ぶpathなので、この二成分を横切る辺 $f\in C\setminus\{e\}$ が少なくとも一本あります。
$e$ はcycle上の最重量辺なので $w(f)\le w(e)$ です。cut交換定理により
$$
T'=T-e+f
$$
はspanning treeで、
$$
w(T')=w(T)-w(e)+w(f)\le w(T).
$$
従って $T'$ もMSTで、$e$ を含みません。
$e$ が一意な最重量辺なら $w(f)< w(e)$ です。$e$ を含むMSTを仮定すると上の交換でさらに軽いspanning treeができて矛盾します。従ってどのMSTも $e$ を含みません。□
cut propertyは「採用してよい辺」、cycle propertyは「除外してよい辺」を与えます。Kruskal算法はcycleを作らない最軽量辺を採用し、Prim算法は一つの成長中の頂点集合から外へ出る最軽量辺を採用します。
forestを壊さない安全辺
算法の途中では、まだspanning treeではなく複数成分からなるforestを持ちます。
$G$ のforest $F$ が最小全域木へ拡張可能な森|MSTへ拡張可能であるとは、あるMST $T$ が存在して
$$
E(F)\subseteq E(T)
$$
となることをいう。
$F$ をMSTへ拡張可能なspanning forestとする。相異なる $F$-成分を結ぶ全辺の中から最軽量辺 $e$ を選ぶ。このとき $F+e$ もMSTへ拡張可能である。
$F$ を含むMST $T$ を取ります。$e\in T$ なら同じ $T$ が $F+e$ を含みます。
$e=uv\notin T$ とします。$u$ を含む $F$-成分の頂点集合を $S$ とします。$v$ は別の $F$-成分にあるので $e\in\delta(S)$ です。$T+e$ の基本cycleはcut $\delta(S)$ を $e$ 以外の辺 $f$ でも横切ります。
$F$ の辺は一つの $F$-成分の内部にしかないので、cutを横切る $f$ は $F$ に属しません。また $f$ は相異なる $F$-成分を結ぶ辺です。$e$ の選び方から
$$
w(e)\le w(f).
$$
従って $T'=T+e-f$ はMSTであり、$F+e$ を含みます。よって $F+e$ はMSTへ拡張可能です。□
この補題では、同率辺のどれを選んでも「その選択を含むMST」へ交換できます。未来の選択肢を完全に固定しなくても、少なくとも一つの最適解へ延長できるという不変量を保ちます。
Kruskal算法
入力：有限連結weighted graph $G=(V,E)$。
- 辺を重みの非減少順に並べる。同率辺の順序は任意とする。
- $F$ を全頂点と辺0本からなるforestとする。
- 並べた順に辺 $e$ を調べる。
- $F+e$ がcycleを作らない、すなわち $e$ の両端が異なる $F$-成分にあるなら $e$ を採用する。
- $|V|-1$ 本を採用したら出力する。
Kruskal算法は停止し、MSTを出力する。
採用辺集合 $F$ がMSTへ拡張可能であることを不変量にします。初期forestは空辺集合であり、任意のMSTに含まれるので拡張可能です。
Kruskalが辺 $e$ を採用する時点で、$e$ は相異なる $F$-成分を結びます。また、それより軽い辺はすべて既に調べられています。もし相異なる $F$-成分を結ぶより軽い辺があれば、その辺を調べた時点でも両端は異なる成分にあり、採用されていたはずです。従って $e$ は現在の相異なる成分を結ぶ全辺の中で最軽量です。安全辺補題により $F+e$ もMSTへ拡張可能です。
cycleを作る辺は採用しないので、$F$ は常にforestです。もし全辺を調べても $F$ が非連結なら、$G$ の連結性により異なる $F$-成分を結ぶ辺があります。その辺は調べた時点でcycleを作らず採用されたはずなので矛盾です。従って最終的に $F$ は連結となり、$|V|-1$ 辺のspanning treeです。
終了時の $F$ はあるMST $T$ に含まれます。しかし $F,T$ はともに $|V|-1$ 本の辺をもつので $F=T$ です。従って出力はMSTです。□
cycle判定と実行時間
単純な実装では、辺を採用するたびにDFSで両端が既に同じ成分か調べられます。辺数を $m$、頂点数を $n$ とすると、sortingに $O(m\log m)$、各辺のDFSに $O(n+m)$ かかるため、全体を
$$
O(m\log m+m(n+m))
$$
で実行できます。
より速い初等的実装として、各頂点に現在の成分番号を記録し、各成分の頂点listと大きさを持ちます。辺の両端の成分番号は $O(1)$ で比較できます。二成分を併合するときは、小さい方のlistに属する全頂点の成分番号を大きい方へ書き換えます。
一頂点の番号が書き換わるたび、その頂点が新たに属する成分の大きさは以前の少なくとも2倍です。成分の大きさは $n$ を超えないため、一頂点の番号は高々 $\lfloor\log_2 n\rfloor$ 回しか書き換わりません。従って全併合に要する書換えは $O(n\log n)$ 回です。sortingの $O(m\log m)$ と各辺の定数時間判定を合わせ、連結グラフでは $m\ge n-1$ なので全体は $O(m\log m)$ 時間、$O(n+m)$ 空間で実行できます。さらに高速なunion by rankとpath compressionもありますが、上の実装だけでこの評価は完結しています。
Prim算法
Kruskal算法が複数の木を同時に育てるのに対し、Prim算法は一つの木だけを育てます。
入力：有限連結weighted graph $G=(V,E)$ と開始頂点 $r$。
- $S=\{r\}$、$F=\varnothing$ とする。
- $S\ne V$ の間、cut $\delta(S)$ 上の最軽量辺 $e=uv$ を選ぶ。ただし $u\in S,v\notin S$ とする。
- $e$ を $F$ に加え、$v$ を $S$ に加える。
- $F$ を出力する。
$G$ は連結なので $S\ne V$ なら $\delta(S)$ は空ではありません。
Prim算法は任意の開始頂点からMSTを出力する。
各段階で、$F$ は頂点集合 $S$ を結ぶ木であり、あるMSTに含まれることを不変量にします。初期状態では一頂点と空辺集合なので成立します。
選んだ $e$ はcut $\delta(S)$ の最軽量辺です。$F$ を含むMST $T$ を一つ取ります。$e\notin T$ なら、cut propertyの証明と同じ交換を行います。$T+e$ のcycleには $e$ 以外のcut辺 $f$ があり、$F$ の辺はすべて $S$ 内部にあるため $f\notin F$ です。$w(e)\le w(f)$ なので $T+e-f$ は $F+e$ を含むMSTです。従って拡張可能性が保たれます。
$e$ は新頂点 $v$ を既存の木へ一本だけで接続するため、cycleを作らず、$F+e$ は $S\cup\{v\}$ を結ぶ木です。各反復で $|S|$ が1増えるので $n-1$ 回で $S=V$ となります。そのとき $F$ はspanning treeで、あるMSTに含まれ、辺数が等しいためそれ自身がMSTです。□
隣接行列から毎回cut辺を走査する単純実装は $O(n^2)$ 時間で実行できます。疎なグラフでは、各未採用頂点について現在の $S$ へつなぐ最軽量辺をpriority queueで管理すると、binary heapの挿入・更新・削除最小の各操作が $O(\log n)$ であり、全辺を高々定数回調べて $O(m\log n)$ 時間になります。
同率重みとMSTの一意性
同率重みがあるからといって必ず複数のMSTがあるわけではありません。しかし全辺重みが相異なれば一意性を保証できます。
有限連結weighted graphで全ての辺重みが互いに異なるなら、MSTはただ一つである。
相異なる二つのMST $T_1,T_2$ があると仮定します。対称差
$$
E(T_1)\triangle E(T_2)
$$
の中で最も軽い辺を $e$ とし、必要なら番号を交換して $e\in T_1\setminus T_2$ とします。
$T_2+e$ の基本cycleは、$T_1-e$ が作るcutを横切る辺 $f\in T_2\setminus T_1$ を含みます。$e,f$ はともに対称差にあり、$e$ をその中の最軽量辺に選び、重みは相異なるので
$$
w(e)< w(f).
$$
cycle交換により $T_2+e-f$ はspanning treeで、その重みは
$$
w(T_2)+w(e)-w(f)< w(T_2)
$$
です。これは $T_2$ がMSTであることに反します。従ってMSTは一意です。□
逆は偽です。三角形の辺重みを1,1,2とすると、重み1の二辺を使うspanning treeだけが重み2で最小です。同率辺があってもMSTは一意です。
$T_1,T_2$ を同じweighted graphの異なるMSTとする。$T_1\triangle T_2$ 内の最軽量辺 $e$ が $T_1\setminus T_2$ に属するとする。このとき、ある $f\in T_2\setminus T_1$ が存在して
$$
w(e)=w(f)
$$
であり、$T_1-e+f$ と $T_2-f+e$ はともにMSTになる。
「全域木と切断・閉路の性質」の対称交換定理の証明どおり、$T_1-e$ のcutを横切り、$T_2+e$ の基本cycle上にある $f\in T_2\setminus T_1$ を選べます。両方の交換後はspanning treeです。
$e$ は対称差内の最軽量辺なので $w(e)\le w(f)$ です。$T_2-f+e$ がspanning treeであり、$T_2$ はMSTなので
$$
w(T_2)-w(f)+w(e)\ge w(T_2),
$$
従って $w(e)\ge w(f)$ です。両方から $w(e)=w(f)$ を得ます。そのため交換後の二木の重みは元のMSTと等しく、どちらもMSTです。□
KruskalとPrimを同じ例で動かす
頂点 $A,B,C,D,E$ と次の重み付き辺を考えます。
$$
\begin{array}{c|ccccccc}
\text{辺}&AB&AC&BC&BD&CD&CE&DE\\ \hline
\text{重み}&1&4&2&5&1&3&2
\end{array}
$$
Kruskal算法では重み順に $AB(1),CD(1),BC(2),DE(2),CE(3),AC(4),BD(5)$ と調べます。
- $AB,CD$ を採用する。
- $BC$ は二成分を結ぶので採用する。
- $DE$ は新頂点 $E$ の成分を結ぶので採用する。
- 4辺で5頂点が一つにつながったので終了する。
得る木は
$$ \{AB,BC,CD,DE\},\qquad w=1+2+1+2=6. $$
Prim算法を $A$ から始めると、cut上の最軽量辺を順に
$$ AB(1), BC(2), CD(1), DE(2) $$
と選び、同じ木を得ます。選択順は違っても、交換原理が最適性を保証します。
演習
頂点 $1,2,3,4$ と辺重み
$$
w(12)=1,\quad w(13)=3,\quad w(14)=4,\quad
w(23)=2,\quad w(24)=5,\quad w(34)=1
$$
をもつ $K_4$ にKruskal算法を適用し、採用・棄却の理由とMSTの重みを書け。
重み順は $12(1),34(1),23(2),13(3),14(4),24(5)$ です。最初の12と34はcycleを作らないので採用します。23は成分 $\{1,2\}$ と $\{3,4\}$ を結ぶので採用します。この時点で4頂点を結ぶ3辺の木ができ、終了します。
得るMSTは
$$
\{12,34,23\},\qquad w=1+1+2=4.
$$
13以降を調べる実装なら、13はcycle $1,2,3,1$ を作るため棄却されます。既にspanning treeが完成しているので残りは不要です。□
直前の $K_4$ で、頂点4からPrim算法を実行せよ。同率がないので各段階の選択を明示し、Kruskal算法と同じMSTになることを確認せよ。
$S=\{4\}$ から出る辺は34(1),14(4),24(5)なので34を選びます。$S=\{3,4\}$ から外へ出る辺は23(2),13(3),14(4),24(5)なので23を選びます。$S=\{2,3,4\}$ から残る頂点1へ出る辺は12(1),13(3),14(4)なので12を選びます。
得る辺集合は
$$
\{34,23,12\}
$$
で、Kruskalの出力と同じ、重み4のMSTです。□
連結weighted graphで、ある頂点 $v$ に接続する辺の重みが全て相異なり、その中で $e$ が最軽量であるとする。$e$ がすべてのMSTに含まれることを示せ。
cut $\delta(\{v\})$ は $v$ に接続する全辺からなります。仮定により $e$ はこのcut上の一意な最軽量辺です。cut propertyの一意性部分から、すべてのMSTが $e$ を含みます。□
辺重み付きcycle
$$
v_1v_2\cdots v_kv_1
$$
で、辺 $v_kv_1$ の重みが他の全辺より真に大きい。このcycleを含む任意の連結グラフのMSTが $v_kv_1$ を含まないことを示せ。
$v_kv_1$ は与えられたcycle上の一意な最重量辺です。cycle propertyの一意性部分から、その辺を含むMSTは存在しません。グラフのcycle外にどのような辺があっても、このcycle内の交換だけで重い辺を除けるため結論は変わりません。□
四角形 $C_4$ の各辺重みを1とし、対角線一本の重みを2とする。このグラフのMSTをすべて列挙し、Kruskal算法の同率辺の順序により出力が変わり得ることを説明せよ。
四角形の辺だけから三辺を選び、cycleを切ったものはspanning treeで重み3です。四角形の四辺のうちどれを除くかにより4通りあります。
対角線を含むspanning treeは、残り二辺の重みが各1なので総重みは少なくとも4です。従ってMSTは四角形から一辺を除いた4本、正確には4通りです。
Kruskal算法は重み1の四辺を任意順に調べ、最初の三辺がcycleを作らなければ採用します。四本目はcycleを作り棄却されます。同率辺の順序により棄却される四角形辺が変わるため、4通りのMSTが出力され得ます。□
三角形の辺重みが $-5,-2,4$ である。MSTを求め、Kruskal・Primの証明が負の重みでも変わらない理由を述べよ。
三頂点のspanning treeは三辺から二辺を選んだものです。最軽量の二辺 $-5,-2$ を選ぶと総重みは $-7$ で、他は $-1$ または2です。従ってMSTは重み $-5,-2$ の二辺です。
Kruskal算法は重みの大小順しか使わず、負かどうかを使いません。Prim算法とcut propertyの交換式
$$
w(T+e-f)=w(T)+w(e)-w(f)
$$
も $w(e)\le w(f)$ だけを使います。従って負の重みでも証明はそのまま成立します。□
本章で得たもの
cut上の最軽量辺はあるMSTへ安全に取り込め、cycle上の最重量辺はあるMSTから安全に除けます。「全域木と切断・閉路の性質」の交換法則に重み比較を加えるだけで、KruskalとPrimという異なるgreedy算法の正当性を同じ不変量から証明できました。
$$
n^{n-2}
$$
であるCayley公式を全単射として証明します。
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
