最小全域木（クラスカル法・プリム法）

木の辺数が $∣ V ∣ - 1$ であることと、カット性質（カットを横切る最小の重みの辺は最小全域木に含まれる）を使える。クラスカル法やプリム法で、重みつき連結グラフの最小全域木の重みを求められる

前提

グラフの次数と握手補題（大学数学グラフ理論）

この技能までの道筋（6 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）

説明

重みつきの連結グラフでは、すべての頂点をつなぎ閉路を含まない辺の集まりを全域木といいます。この技能では、全域木のうち重みの合計が最小のもの（最小全域木）を求めます。送電網や通信網を最も安くつなぐ問題などで使います。クラスカル法では「軽い辺から順に、閉路ができない限り採用する」、プリム法では「1 頂点から木を広げ、毎回いちばん軽い辺で 1 頂点ずつ取り込む」という手順で求めます。

なぜそうしてよいのか

まず用語を決めます。同じ頂点を 2 度通らずに辺でたどる道を路といい、辺を 3 本以上使って始点に戻る道（始点以外の頂点は重複しない）を閉路といいます。どの 2 頂点も路で結べるグラフを連結といい、連結で閉路をもたないグラフを木といいます。グラフ $G = (V, E)$ の辺の一部を選んで $V$ のすべての頂点を含む木にしたものが全域木です。頂点 $∣ V ∣$ 個の木の辺はちょうど $∣ V ∣ - 1$ 本です。頂点が 2 個以上の木で最も長い路をとると、その端点 $v$ の次数は 1 です（路の外へ辺が出ていれば路を延ばせ、路の上の頂点へ辺が出ていれば閉路ができるからです）。 $v$ とその辺を除いても、残りの 2 頂点を結ぶ路は次数 1 の $v$ を途中で通れないので連結のままで、辺を減らしただけなので閉路もできず、木のままです。これを繰り返すと頂点 1 個・辺 1 本ずつ減り、最後は頂点 1 個・辺 0 本になるので、辺数 $= ∣ V ∣ - 1$ です。また、木の 2 頂点を結ぶ路は 1 本しかありません（2 本あれば、それらが分かれてから再び合流するまでの部分で閉路ができるからです）。

次にカット性質です。 $V$ を空でない 2 つの部分 $S$ と $V ∖ S$ に分けたものをカットといい、両端が別々の側にある辺を「カットを横切る辺」といいます。カット性質とは次の主張です。「辺の集合 $A$ がある最小全域木に含まれ、 $A$ のどの辺もカットを横切らないとする。カットを横切る辺のうち重みが最小の辺を $e = uv$ （ $u \in S, v \in / S$ ）とすると、 $A \cup {e}$ を含む最小全域木も存在する。」理由： $A$ を含む最小全域木 $T$ が $e$ を含めばそれで終わりです。含まないとき、 $T$ に $e$ を加えると、できる閉路は $e$ と $T$ 内の $u$ - $v$ 路を合わせたものに限られ、その路は 1 本しかないので、閉路はちょうど 1 つ $C$ です。 $T$ 内の $u$ - $v$ 路は $S$ から $V ∖ S$ へ移るので、カットを横切る辺 $f$ を含みます。 $f$ は $T$ の辺なので $e$ とは異なり、カットを横切るので $A$ には属しません。 $T$ に $e$ を加えて $f$ を除いたものを $T^{'}$ とします。 $f$ の両端は $C$ の残りの部分でつながるので $T^{'}$ は連結で、唯一の閉路 $C$ が $f$ を失って壊れるので閉路もなく、 $T^{'}$ は全域木です。重みは $w (e) - w (f) \leq 0$ だけ変わるので増えず、 $T^{'}$ も最小全域木で、しかも $A \cup {e}$ を含みます。

これで二つの方法が正しいことを帰納法で示せます。主張は「採用済みの辺の集合 $A$ は、いつでもある最小全域木に含まれる」です。はじめ $A$ は空で、連結グラフは閉路の辺を 1 本ずつ除けば全域木をもち、全域木は有限個なので最小全域木があり、主張は成り立ちます。クラスカル法で $e = uv$ を採用するとき、 $u$ を含む塊（ $A$ の辺でつながった頂点の集まり）を $S$ とします。 $A$ の辺は塊の内部にあるので、カットを横切りません。 $e$ より前に見た辺は、採用されて $A$ に入ったか、そのとき同じ塊の中にあって捨てられたかのどちらかです。塊は合わさって大きくなるだけなので、どちらも今のカットを横切りません。後で見る辺の重みは $w (e)$ 以上なので、 $e$ はカットを横切る最小辺であり、カット性質から採用後も主張が保たれます。プリム法では、育てている木の頂点集合を $S$ とすれば同じ議論がそのまま使えます。最後に $A$ は閉路をもたず、すべての頂点をつなぐ全域木になります（つながっていない塊が残っていれば、それらを結ぶ辺が見られたときに採用されていたはずです）。 $A$ も、 $A$ を含む最小全域木も辺は $∣ V ∣ - 1$ 本なので、両者は一致し、 $A$ が最小全域木です。

手順

グラフが連結であることを確かめ、頂点数 $∣ V ∣$ から、採用すべき辺の本数 $∣ V ∣ - 1$ を求める。
（クラスカル法）辺を重みの小さい順に並べる。重みが等しい辺の順はどちらが先でもよい。
並べた順に辺を見る。両端がまだ別々の塊にあれば採用し（2 つの塊が 1 つになる）、すでに同じ塊にあれば閉路ができるので捨てる。
採用した辺が $∣ V ∣ - 1$ 本になったら終了し、その重みの合計を最小全域木の重みとする。
（別法：プリム法）1 頂点だけの集合 $S$ から始める。 $S$ と $V ∖ S$ を結ぶすべての辺のうち最も軽いものを採用し、その端点を $S$ に加える。これを $S = V$ になるまで繰り返す。

例題

頂点集合 $V = {a, b, c, d, e}$ 、辺と重みが $ab : 4, a c : 1, b c : 2, b d : 5, c d : 8, ce : 10, d e : 3, b e : 7$ である重みつき連結グラフの最小全域木の重みを求めよ。

例題の解答

手順 1： $∣ V ∣ = 5$ なので、採用する辺は $5 - 1 = 4$ 本である。
手順 2：辺を重みの小さい順に並べると $a c (1), b c (2), d e (3), ab (4), b d (5), b e (7), c d (8), ce (10)$ となる。
手順 3：順に見ていく。
- $a c$ ： $a, c$ は別々の塊なので採用する。塊は ${a, c}, {b}, {d}, {e}$ になる。
- $b c$ ：採用する。塊は ${a, b, c}, {d}, {e}$ になる。
- $d e$ ：採用する。塊は ${a, b, c}, {d, e}$ になる。
- $ab$ ：両端がともに ${a, b, c}$ にあり、閉路 $a \to b \to c \to a$ ができるので捨てる。
- $b d$ ：2 つの塊を結ぶので採用する。塊は ${a, b, c, d, e}$ になる。
手順 4：採用した辺は $a c, b c, d e, b d$ の 4 本で、 $∣ V ∣ - 1$ 本に達したので終了する。重みの合計は $1 + 2 + 3 + 5 = 11$ である。
（確認：手順 5 のプリム法で $a$ から始めると、 $S = {a}$ から $a c (1)$ 、 $S = {a, c}$ から $b c (2)$ 、 $S = {a, b, c}$ から $b d (5)$ 、 $S = {a, b, c, d}$ から $d e (3)$ が採用され、合計は同じく $11$ になる。）

答え: $11$

よくある誤り

重みの小さい辺を、閉路を気にせず $∣ V ∣ - 1$ 本取ってしまう誤り。例題では $1 + 2 + 3 + 4 = 10$ となるが、 $a c, b c, ab$ は閉路をつくり、 ${d, e}$ が他の頂点とつながらないので全域木ではない。正しくは $ab$ を捨てて $b d$ を採用し、合計は $1 + 2 + 3 + 5 = 11$ である。
「各頂点に接する辺のうち最も軽いものを全部集めれば全域木になる」としてしまう誤り。例題では各頂点 $a, b, c, d, e$ の最軽辺は $a c, b c, a c, d e, d e$ で、集めても ${a c, b c, d e}$ の 3 本にしかならず、連結にならない。正しくは、辺数が $∣ V ∣ - 1 = 4$ になるまでクラスカル法やプリム法を続ける。
プリム法で、直前に加えた頂点に接する辺だけから最小のものを選んでしまう誤り。例題で $a$ から始めて $a c, b c$ の次に $b$ に接する辺だけを見ても結果は同じだが、一般には誤る。正しくは、木の頂点集合 $S$ 全体と $V ∖ S$ を結ぶすべての辺の中から最小のものを選ぶ。カット性質が保証するのは、カット $(S, V ∖ S)$ を横切る辺の中で最小の辺だけである。
カット性質を「カットを横切る最小の辺はすべての最小全域木に含まれる」と言い切ってしまう誤り。同じ重みの辺があると成り立たないことがある。たとえば $K_{3}$ で 3 辺の重みがすべて $1$ なら、どの 2 辺を選んでも最小全域木で、カット $({a}, {b, c})$ を横切る最小辺 $ab$ を含まない最小全域木 ${a c, b c}$ もある。正しくは「最小の辺を含む最小全域木が存在する」である。なお、重みがすべて異なるときは、カットを横切る最小辺が 1 本に決まり、入れ替えで重みが真に減るので、その辺はすべての最小全域木に含まれる（これは十分条件であり、重みが重なっていても最小辺が 1 本だけならやはり成り立つ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

マトロイドの独立集合・基・階数（大学院数学凸最適化・組合せ最適化）