最小生成树（MST）

算法导论 Exercises 23.1-8

Let T be a minimum spanning tree of a graph G, and let L be the sorted list of the edge weights of T . Show that for any other minimum spanning tree T' of G, the list L is also the sorted list of edge weights of T'.

假设最小生成树有 n 条边, 存在两个最小生成树 A 和 B, 用 w(e) 表示边的权值.

A 权值递增排列 w(a1) <= w(a2) <= ... w(an)

B 权值递增排列 w(b1) <= w(b2) <= ... w(bn)

假设 i 是两个列表中, 第一次出现边不同的位置, 即 ai ≠ bi。不妨设 w(ai) >= w(bi).

情况1。如果 A 中含有边 bi, 由于 ai 和 bi 在列表 i 位置之前都是相同的, 若含有 bi 则一定在 i 位置后, 即有 j > i 使得 bi=aj。得到 w(bi) = w(aj) >= w(ai) >= w(bi), 即 w(bi) = w(aj) = w(ai), 故 i 位置处边的权值相同。在树A的边列表中交换边ai和aj的位置，并不会影响树A的边权列表里值的顺序，因而两棵树在第i个位置的边变成同一条边。

情况2, 如果 A 不包含边 bi, 则把 bi 加到 A 中, 会在某处形成一个圈. 由于 A 是最小生成树, 圈内任何一条边的权值都<= w(bi)。另外这个圈中必定存在 aj 不在 B 中（如果圈内所有边都在B中，那么B就有环，不是MST了）, 得出 w(aj) <= w(bi) 且 j > i（如果j<i，那么aj在A和B的共享序列中，那么aj也就在B中）. 

因此 w(bi) <= w(ai) <= w(aj) <= w(bi), 即 w(bi) = w(aj) = w(ai), 故 i 位置处边的权值仍相同。那么在A中，把aj换成bi，仍然能保持A是MST，并且不会影响树A的边权列表里值的顺序。从而化归为情况1。