最小生成树的相关性质及其理解

1 ） ** ** 定义为在任意一棵树中添加一条边并在由此产生的环中移除一条边称为一次操作。（即通过替换一条边并确保结果仍为树）因此，在无向图中给定两个生成树A和B时，则A可以通过若干次操作转换为B。

证

注：这个命题相对容易证明，并且它说明任何两棵生成树都可以通过逐步更换边来实现。（特别强调，在换边的过程中始终保证每一步都是一个连通且无环的图结构）。

通过若干次操作，并没有特别的意义

（ 2） 将该图的所有生成树边按照递增顺序进行排序后得到一个有序权重序列，则任何两个最小生成树都具有相同的有序权重序列。（算法导论 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相等。实际上，在这种情况下有 bi与 aj具有相同的权重值 w(bi)=w(aj)，而 ai的权重值同样不低于它们。调换ai和 aj在树A中的位置不会改变该树各处的权值排序特性；