グラフ理論の問題

クラスカル法を使います。クラスカル法では、重みの小さい辺から順に調べます。その辺を加えても閉路ができなければ採用し、閉路ができるなら捨てます。頂点数は $6$ なので、全域木の辺数は $|V|-1=5$ です。$5$ 本を採用した時点で終わります。

手順 1：辺を重みの小さい順に並べる
$$EF(1),AC(2),CD(3),AB(4),BC(5),DE(6),BD(7),CE(8),DF(9)$$

手順 2：順に調べる（採用した辺でつながっている頂点のまとまりを $\{\}$ で書きます）
- $EF(1)$：$E$ と $F$ は別のまとまりなので採用します。まとまりは $\{E,F\}$ になります。
- $AC(2)$：$A$ と $C$ は別のまとまりなので採用します。まとまりは $\{A,C\}$, $\{E,F\}$ です。
- $CD(3)$：$D$ はまだどのまとまりにも入っていないので採用します。まとまりは $\{A,C,D\}$, $\{E,F\}$ です。
- $AB(4)$：$B$ はまだどのまとまりにも入っていないので採用します。まとまりは $\{A,B,C,D\}$, $\{E,F\}$ です。
- $BC(5)$：$B$ と $C$ はすでに同じまとまりにあります。加えると閉路 $A\text{-}B\text{-}C\text{-}A$ ができるので捨てます。
- $DE(6)$：$D$ と $E$ は別のまとまりなので採用します。まとまりは $\{A,B,C,D,E,F\}$ になります。

これで $5$ 本（$=|V|-1$）を採用し、すべての頂点がつながったので終了です。

手順 3：重みを足す
採用した辺は $EF,AC,CD,AB,DE$ です。重みの和は
$$1+2+3+4+6=16$$
となります。

（確認）カット性質からも確かめられます。$\{E,F\}$ と残りの頂点 $\{A,B,C,D\}$ に分けるカットを横切る辺は $CE(8)$, $DE(6)$, $DF(9)$ です。このうち重みが最小の $DE$ は、必ず最小全域木に含まれます。

よって、最小全域木の重みは $16$ です。

クラスカル法を使う。辺を重みの小さい順に並べると EF:1, AC:2, CD:3, AB:4, BC:5, DE:6, BD:7, CE:8, DF:9 となる。
1. EF(1) を採用する。{E,F}
2. AC(2) を採用する。{A,C}
3. CD(3) を採用する。{A,C,D}
4. AB(4) を採用する。{A,B,C,D}
5. BC(5) は B と C がすでに同じ連結成分にあるので閉路になり、不採用。
6. DE(6) を採用する。{A,B,C,D} と {E,F} がつながり、全頂点が連結になる。
採用した辺は EF, AC, CD, AB, DE の 5 本で、頂点数 6 より 1 少ないので完成である。
重みの和は 1+2+3+4+6=16。
検算として、プリム法を A から始める。AC(2)、CD(3)、AB(4) を採用する。次に外へ出る辺の最小は DE(6) で、これを採用する。最後に EF(1) を採用する。合計は 2+3+4+6+1=16 となり一致する。