グラフ理論の問題

各頂点 $v$ について、$v$ に接続する辺の重みの最小値を $m(v)$ とおく。

$m(v)$ の計算. $x\ne v$ のとき $\mathrm{lcm}(v,x)\ge v$ である。

• $v$ が合成数のとき：$2$ 以上の真の約数 $d$ をもつ。$d\in V$ であり、$\mathrm{lcm}(v,d)=v$ となる。よって $m(v)=v$ である。
• $v=p$ が奇素数のとき：$x\in V$, $x\ne p$ を考える。$p\mid x$ ならば $x\ge 2p$ なので $\mathrm{lcm}(p,x)=x\ge 2p$ である。$p\nmid x$ ならば $\mathrm{lcm}(p,x)=px\ge 2p$ である。また $x=2$ のとき $\mathrm{lcm}(p,2)=2p$ となる。よって $m(p)=2p$ である。

下界. 任意の全域木 $T$ を頂点 $2$ を根とする根つき木とみる。根以外の各頂点 $v$ には、親へ向かう辺 $e_v$ がただ 1 本ある。$v\mapsto e_v$ は、根以外の $28$ 個の頂点と $T$ の $28$ 本の辺との全単射である。さらに $w(e_v)\ge m(v)$ なので、
$$w(T)=\sum _{v\ne 2}w(e_v)\ge \sum _{v\ne 2}m(v)$$
が成り立つ。

構成. 次のように辺を選ぶ。

• 各合成数 $v$ について、$v$ とその真の約数 $d(\ge 2)$ の 1 つを結ぶ（重み $v$）。
• 各奇素数 $p$ について、$p$ と $2$ を結ぶ（重み $2p$）。

このとき、$2$ 以外の各頂点からそれより小さい頂点へ辺がちょうど 1 本出ている。辺は $28$ 本で、閉路はない（閉路上で最大の頂点からは、より小さい頂点への辺が 2 本出ることになり矛盾する）。したがってこれは全域木であり、重みは下界 ${\sum }_{v\ne 2}m(v)$ に一致する。よって最小全域木の重みは ${\sum }_{v\ne 2}m(v)$ である。

計算.

• $2$ から $30$ までの和は $\frac{30\cdot 31}{2}-1=464$ である。
• $30$ 以下の素数は $2,3,5,7,11,13,17,19,23,29$ で、その和は $129$ である。
• 合成数の和は $464-129=335$ である。
• 奇素数の和は $129-2=127$ なので、その寄与は $2\times 127=254$ である。

したがって、最小全域木の重みは $335+254=589$ である。

クラスカル法で、辺を重み（最小公倍数）の小さい順に見ていく。重み $w$ の辺には、$w$ の約数 $d$ と $w$ を結ぶ辺（重み $w$）が必ず含まれる。それ以外に、$\mathrm{lcm}=w$ となる約数でない組もある。

$w=2,3,\dots ,30$ の順に、新しく併合される回数（採用される辺の本数）を調べる。
- $w=4$：$\{2,4\}$ をつなぐ。1 本。
- $w=6$：$3$ と $6$ が新しく加わる。2 本。
- $w=8,9,12,15,16,18,20,21,24,25,27,28,30$：$w$ 自身だけが新しく加わる。各 1 本。
- $w=10,14,22,26$：$p=5,7,11,13$ と $2p$ が新しく加わる。各 2 本。
- $w=15$：$3$ と $5$ は $6$、$10$ を通じてすでに連結しているので、$15$ が加わる 1 本のみ。

重みの合計は
$4+12+8+9+20+12+28+15+16+18+20+21+44+24+25+52+27+28+30=413$

これで採用した辺は 24 本になる。

素数 $17,19,23,29$ は $2$ 倍が範囲外で、どの頂点とも約数関係にない。それぞれの辺の重みは $\mathrm{lcm}(p,j)=pj\ge 2p$ なので、最小の辺は $2$ との辺で、重みは $34,38,46,58$。合計 $176$。これで全体の辺は $24+4=28=29-1$ 本となり、全域木になる。

以上より、最小全域木の重みは $413+176=589$。

検算：辺の本数が $28$ であること、各頂点の接続辺が下限（素数 $p\le 15$ は $2p$、素数 $p\ge 17$ は $2p$）を満たしていることを確認した。