题解

假设最小生成树$T$和$T’$按照权重排序后的边为$(e_0,e_1,…)$和$(e_0’, e_1’,…)$, 引入记号$E_i$和$E_i’$，分别为$T$和$T’$的第$0$到第$i$条边的集合

假设$e_k$和$e_k’$为第一对不是同一条边的位置，假设$e_k$为边$(u, v)$, $e_k’$为$(u’, v’)$，且此时$(u,v)$不在$T’$中

证明第一部分：

在$T’$中必然有一条$u->v$的路径，记为$P’(u,v)$：

  1. $P’(u,v)$不可能只包含$E_{k-1}’$中的边：因为$k$为第一对不同的边故$E_{k-1} = E_{k-1}’$，如果​$u->v$只有$E_{k-1}’$的边则在$T$中形成环路。
  1. 假设边$e_j’$为${P’(u,v)-E_{k-1}’}$中一条，则$weight(e_j’)<=weight(e_k)$ （否则可以在$T’$中把$e_j’$去掉换成$e_k$得到更小的生成树，与$T’$为最小生成树的前提矛盾）, 且$j>=k$，故$weight(e_k’)<=weight(e_k)$

结论1： 对称的可以推到$weight(e_k)<=weight(e_k’)$, 因此$e_k$和$e_k’$的权重必然相等；

结论2： 任取边$e’$属于${P’(u,v)-E_{k-1}’}$, $weight(e’)=weight(e_k)=weight(e_k’)$

证明第二部分：

依次考虑每一个不相等的位置

  1. 设$weight(e_k)<=weight(e_k’)$，如果$T’$中也有$e_k$，则此时用不到以上结论，直接在$T’$中交换$e_k$和$e_k’$（因为$E_{k-1} = E_{k-1}’$，此时$T’$中$e_k$一定在$e_k’$后面，由此同样可知$weight(e_k)=weight(e_k’)$）
  2. 如果$T’$中不包含$e_k$, 可以将${P’(u,v)-E_{k-1}’}$中任意一条替换为$e_k$, 然后转到第$1$步

由以上结论可知，$T’$可以在不改变边权集合的情况下变化为$T$，所以$T’$与$T$的边权集合相同，结论得证

这个命题同样说明，如果无向图的边权都不相同，则最小生成树是唯一的。