グラフ理論の問題

クラスカル法で、重みの小さい辺から順に、閉路を作らないものを採用していく。

まず、重みが $13$ 以下の辺をすべて挙げる。$\mathrm{lcm}(i,j)\ge \max \{i,j\}$ であり、等号は一方が他方の約数のときに限ることに注意して調べると、
$$\begin{array}{ll}4:& \{2,4\}\\ 6:& \{2,3\},\{2,6\},\{3,6\}\\ 8:& \{2,8\},\{4,8\}\\ 9:& \{3,9\}\\ 10:& \{2,5\},\{2,10\},\{5,10\}\\ 12:& \{3,4\},\{4,6\}\end{array}$$
である（頂点 $7$ を含む辺の重みは $\mathrm{lcm}(7,j)=7j\ge 14$ である）。

クラスカル法を実行する。
- 重み $4$: $\{2,4\}$ を採用。
- 重み $6$: $\{2,3\}$, $\{2,6\}$ を採用。$\{3,6\}$ は閉路 $2$-$3$-$6$ を作るので不採用。
- 重み $8$: $\{2,8\}$ を採用。$\{4,8\}$ は閉路を作るので不採用。
- 重み $9$: $\{3,9\}$ を採用。
- 重み $10$: $\{2,5\}$, $\{2,10\}$ を採用。$\{5,10\}$ は閉路を作るので不採用。

この時点で頂点 $2,3,4,5,6,8,9,10$ が 1 つの連結成分になり、採用した辺は $7$ 本である。重み $12$ の辺はどちらも閉路を作るので不採用。残る頂点 $7$ を含む辺のうち最小の重みは $\mathrm{lcm}(7,2)=14$ なので、$\{2,7\}$ を採用して $8$ 本となり、全域木が完成する。

よって最小全域木の重みは
$$4+6+6+8+9+10+10+14=67$$
である。

クラスカル法で辺を重みの小さい順に見る。
重み 4: $\{2,4\}$ を採用。
重み 6: $\{2,3\}$、$\{2,6\}$ を採用($\{3,6\}$ は閉路になるので不採用)。
重み 8: $\{2,8\}$ を採用($\{4,8\}$ は閉路)。
重み 9: $\{3,9\}$ を採用。
重み 10: $\{2,5\}$、$\{2,10\}$ を採用($\{5,10\}$ は閉路)。
ここまでで頂点 $2,3,4,5,6,8,9,10$ が連結。残る頂点 $7$ は他の頂点との最小公倍数が $7k$($k=2,\dots ,10$ のうち相手が $k$ の倍数でなければ $7\times$相手)で、最小は $\mathrm{lcm}(2,7)=14$。$\{2,7\}$ を採用。
採用辺は 8 本(頂点数 9 より 1 少ない)で、重みの和は $4+6+6+8+9+10+10+14=67$。
検算: 各頂点につき、頂点 $5$ に接する辺の最小は $10$、頂点 $9$ は $9$、頂点 $7$ は $14$ であり、これらの辺は互いに別なので下限が整合する。また各カットで最小の辺を採用している(クラスカル法の正当性)。