グラフ理論の問題

頂点集合が $\{0,1,\dots ,n-1\}$ の完全グラフに重み $w(x,y)=x\oplus y$ を与えたものを $G_n$ とし、その最小全域木の重みを $f(n)$ とする（$f(1)=0$）。求めるものは $f(100)$ である。

準備 1（平行移動で重みは変わらない）. 任意の 0 以上の整数 $c$ について $(x\oplus c)\oplus (y\oplus c)=x\oplus y$ である。よって $x\mapsto x\oplus c$ が頂点集合の間の全単射なら、辺の重みを保つグラフの同型になる。

準備 2（分割と Kruskal 法）. $n\ge 2$ とし、$2^m<n\le 2^{m+1}$ をみたす 0 以上の整数 $m$ をとる。頂点を
$$L=\{0,1,\dots ,2^m-1\},U=\{2^m,\dots ,n-1\}$$
に分ける。$U$ の頂点は 2 進法の第 $m$ 桁（$2^m$ の位）が $1$ で、それより上の桁はすべて $0$ であり、$L$ の頂点は第 $m$ 桁以上がすべて $0$ である。したがって
- $L$ 内の辺、$U$ 内の辺の重みは第 $m$ 桁以上が $0$ なので $2^m$ 未満、
- $L$ と $U$ を結ぶ辺の重みは第 $m$ 桁が $1$ なので $2^m$ 以上で、$w(0,2^m)=2^m$ により最小値は $2^m$

である。

Kruskal 法では重みの小さい辺から順に、閉路を作らない限り採用していく。重み $2^m$ 未満の辺は $L$ 内か $U$ 内の辺だけなので、それらを処理し終えた段階で、$L$ と $U$ のそれぞれについて（その上の完全グラフに対する）Kruskal 法を実行したのと同じになり、$L$ と $U$ それぞれの最小全域木ができている。残りは 2 つの連結成分をつなぐ辺で、Kruskal 法は最も軽い横断辺（重み $2^m$）を 1 本採用して終わる。よって
$$f(n)=(L\text{ の最小全域木の重み})+(U\text{ の最小全域木の重み})+2^m.$$
$L$ 上のグラフは $G_{2^m}$ そのものである。また、$x\mapsto x\oplus 2^m$ は $U$ から $\{0,1,\dots ,n-2^m-1\}$ への全単射なので、準備 1 より $U$ 上のグラフは $G_{n-2^m}$ と同型である。したがって
$$f(n)=f(2^m)+f(n-2^m)+2^m(2^m<n\le 2^{m+1}).$$

$n$ が 2 のべきのとき. $n=2^k$（$k\ge 1$）とすると $m=k-1$ で、$a_k=f(2^k)$ とおくと $a_k=2a_{k-1}+2^{k-1}$、$a_0=f(1)=0$。両辺を $2^k$ で割ると $\frac{a_k}{2^k}=\frac{a_{k-1}}{2^{k-1}}+\frac{1}{2}$ なので $\frac{a_k}{2^k}=\frac{k}{2}$、すなわち
$$f(2^k)=k\cdot 2^{k-1}.$$
とくに $f(4)=4,f(32)=80,f(64)=192$。

$f(100)$ の計算. $64<100\le 128$ より
$$f(100)=f(64)+f(36)+64.$$
$32<36\le 64$ より
$$f(36)=f(32)+f(4)+32=80+4+32=116.$$
よって
$$f(100)=192+116+64=372.$$

（確認）$f(4)=4$ は、辺 $\{0,1\},\{2,3\}$（重み 1）と $\{0,2\}$（重み 2）からなる全域木で実現され、重み $1$ の辺は $\{0,1\},\{2,3\}$ の 2 本しかないことから最小であることも直接確かめられる。

答えは $372$ である。

クラスカル法を、重みの小さい順（重みは $2$ のべき乗または他の値）に考える。$x\oplus y<2^k$ となるのは、$x,y$ の $2$ 進表示で $2^k$ 以上の桁がすべて一致するとき、すなわち $\lfloor x/2^k\rfloor =\lfloor y/2^k\rfloor$ のとき、かつそのときに限る。したがって重み $<2^k$ の辺だけを使った部分グラフの連結成分は、$V$ を長さ $2^k$ のブロック $\{m{2}^k,\dots ,(m+1)2^k-1\}\cap V$ に分けたものであり（各ブロック内では、最上位ビット以外が一致する頂点同士を重み $<2^k$ の辺でたどれるので連結）、成分数は $c_k=\lceil 100/2^k\rceil$ である。

重み $2^k\le w<2^{k+1}$ の辺を加えると成分数は $c_{k+1}$ になるので、最小全域木で重みが $[2^k,2^{k+1})$ の辺は $c_k-c_{k+1}$ 本あり、その重みはちょうど $2^k$ である（$2^k$ の辺で $c_{k+1}$ まで併合できる: ブロックの前半と後半の対応する頂点を結ぶ辺の重みは $2^k$）。

$c_0=100,c_1=50,c_2=25,c_3=13,c_4=7,c_5=4,c_6=2,c_7=1$。

• 重み $1$: $100-50=50$ 本 → $50$
• 重み $2$: $50-25=25$ 本 → $50$
• 重み $4$: $25-13=12$ 本 → $48$
• 重み $8$: $13-7=6$ 本 → $48$
• 重み $16$: $7-4=3$ 本 → $48$
• 重み $32$: $4-2=2$ 本 → $64$
• 重み $64$: $2-1=1$ 本 → $64$

辺の本数は $50+25+12+6+3+2+1=99$ で全域木の辺数 $99$ と一致する。合計は $50+50+48+48+48+64+64=372$。

検算: 各頂点 $v=1,\dots ,99$ を $v-\mathrm{lowbit}(v)$ とつなぐ木（重み $\mathrm{lowbit}(v)$）の総和 ${\sum }_{v=1}^{99}\mathrm{lowbit}(v)={\sum }_k{2}^k(\lfloor 99/2^k\rfloor -\lfloor 99/2^{k+1}\rfloor )=50+50+48+48+48+64+64=372$ と一致する。