23.2-1 对于同一个输入图，Kruskal算法返回的最小生成树可以不同。这种不同来源于对边进行排序时，对权重相同的边进行的不同处理。证明：对于图G的每棵最小生成树T，存在一种办法来对G的边进行排序，使得Kruskal算法所返回的最小生成树就是T。
直接想法就是再加一个在输入时边的顺序（即相同权重看哪条边存储的在前面就选哪条）。。。这能怎么证明><
顺便po上为了解决这个问题顺便复习和思考的内容（对，思考XD
§相关
- Kruskal算法是每次选择权重最小的边加入森林，它的本质是贪心算法。
- 如果该图所有的边均不相同，那么我们可以证明最小生成树唯一
- 如果各边权值唯一，从最小生成树开始，每次加一条边i并在新生成的环上删除最大的一条边j（满足权值$e_i$ < $e_j$），这时会得到一棵新的生成树，如果我们加入的那条边满足 $e_j$- $e_i$最小，那么得到的就是第二小的生成树。从这个第二小的生成树开始，进行同样的操作可以得到第三小的生成树。这个迭代过程中树的权值是一直递增的，所以不可能出现相同权值的多棵最小生成树。
- 对于给定的图而言,因为最小生成树的权值和是确定的,所以最小生成树不唯一当且仅当最小生成树的形状不唯一
- 可证明最小生成树T与任意生成树T’，对边进行排序$w_1$ <= $w_2$ <= … <= $w_n$ , $w_1’$ <= $w_2’$ <= … <= $w_n’$ 有 $w_i’$ <= $w_i’$
- 如果i时第一个有 $w_i’$ < $w_i$，即有$w_n$ >= $w_{n-1}$ >= … >=$w_i$ > $w_i’$ >= $w_{i-1}’$ >= … >= $w_1’$。
- 所以如果我们选择{$w_1’$ … $w_i’$}中某边加入T，要么产生与{$w_1$ … $w_{i-1}$}产生环，要么就是{$w_1$ … $w_{i-1}$}中某边。
- 所以在选择边 $e_1$ … $e_{i-1}$ 后有n-i+1个联通分量，再加入边 $e_1’$ … $e_i’$ 后仍为n-i个联通分量，但事实上，因为来自于生成树T’，所以边 $e_1’$ … $e_i’$ 能够有n-i个联通分量
- 所以矛盾。
§另，最小生成树唯一性判定
- 对图中每条边，扫描其他边，如果存在相同权值的边，则对该边进行标记；
- 然后用Kruskal（或者Prim）算法求MST（最小生成树）；
- 求得MST后，如果该MST中未包含做了标记的边，即可判定MST唯一；如果包含作了标记的边，则依次去掉这些边再求MST，如果求得的MST权值和原MST权值相同，即可判定MST不唯一。
§转
某版23.1-8 把一个连通无向图的生成树边按权值递增排序，称排好序的边权列表为有序边权列表，则任意两棵最小生成树的有序边权列表是相同的。（算法导论）
证： 设最小生成树有n条边，任意两棵最小生成树分别称为A, B, 如果e是一条边，用w(e)表示该边的权值。
A的边按权值递增排序后为a1, a2,……an w(a1)≤w(a2)≤……w(an)
B的边按权值递增排序后为b1, b2,……bn w(b1)≤w(b2)≤……w(bn)
设i是两个边列表中，第一次出现不同边的位置，ai≠bi
不妨设w(ai)≥w(bi)
情形1 如果树A中包含边bi，则一定有j>i使得 bi=aj ,事实上,这时有 w(bi)=w(aj)≥w(ai) ≥w(bi) 故 w(bi)=w(aj)=w(ai)，在树A的边列表中交换边ai和 aj的位置并不会影响树A的边权有序列表，两棵树在第i个位置的边变成同一条边。
情形2 树A中并不包含边bi，则把bi加到树A上，形成一个圈，由于A是最小生成树，这个圈里任意一条边的权值都不大于w(bi) ，另外，这个圈里存在边aj不在树B中。因此，有w(aj)≤w(bi)，且j>i (因为aj不在B中)。于是，有w(bi)≤w(ai)≤w(aj)≤w(bi)，因此 w(ai)= w(aj) = w(bi)。那么在树A中把aj换成bi仍然保持它是一棵最小生成树，并不会影响树A的边权有序列表，并且转换成情形1。