最小生成树的一些性质和理解

1) 定义在一棵树里添加一条边，并在产生的圈里删除一条边叫做一次操作。（也就是说换掉一条边并且保证结果是树），则树A和B是无向图的两个生成树，则A可以通过若干次操作变成B。
 
证：把树看作边的集合，如果B中有一条A没有的边，则把这条边加到A上，A产生一个圈中至少有一条是B中没有的边，把这条边删掉，则A仍然是生成树，A,B集合相同的边多了一条，重复这个过程直到A B包含的边相同。
 
注：这个命题比较容易证，它告诉我们任何两棵生成树都可以通过不断换边得到。（重要的是换边的过程中始终保持是树。）
“可以通过若干次操作”，这个“可以”并没有“特殊”的含义，也就是说我们可以随便加一条B有而A没有的边，总可以找到一条合适的边删掉。

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 ,事实上,这时有 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。
 
注：这个命题说明，如果无向图的边权都不相同，则最小生成树是唯一的。但是其逆命题不成立。即如果无向图的最小生成树唯一，则无向图的边权是可能有相同的。例子，比如原图本身就是一棵树，并且有两条边的边权相等。

3)A,B是同一个无向连通图的两棵不同的最小生成树，则A可以通过若干次（1）中定义的换边操作，并且保证每次结果仍然是最小生成树，最终转换成B。
 
证：做法和（2）类似，也是要找一条树B有但是树A没有的边。事实上（2）的证明过程“情形2”的部分，就已经找到这样一条边了。按照（2）中给出的方法，就可以把A转换成B。
注：上述证明过程证得了和（1）中类似的结论，但是此时的“可以”暂时有“特殊”的含义，至少证明中需要以一定的规则选边。这显得有点不“美观”。那么，是否可以任意选边呢？考虑任意选边造成的“后果”：把任意一条B有而A没有的边加入到A，由于A是最小生成树，所以形成的圈里所有的边的权值都不大于新加的边，那么如果这个圈里没有其他的这种权值的边，换句话说，如果这个圈里的这条边是唯一权值最大的边怎么办呢？或者，如果这个圈里所有和这条边权值相等的边都也在B中，那么该如何保证换边后，A和B相同的边数增多一条呢？下面证明，这些情况不可能出现。
 

4) 一个连通无向图G,不会有一棵最小生成树包含G的一个圈中全部最大权值的边。
 
证：设图的节点集合是V。反证，假设有一棵最小生成树T包含G中某个圈的全部权值最大的边，设其中一条边是e, 则在树中删掉边e，T-e是不连通的，它把节点分成了两部分（连通分量），A和B=V-A。在原图G中，这条边在一个圈C里，且在C中权值是最大的。则(C-e)是G中一条路，这条路中有节点在A中，也有节点在B中，因此必然有一条边e’，它一端在A中，一端在B中,显然它不在T-e中。于是把e’加入到T-e中，这样形成的是一棵树T’。（|V|-1条边的连通图显然是树），而由于w(e’)，有w(T’)，与T是最小生成树矛盾。
 
注：特别地，如果一个圈中权值最大的边唯一，则最小生成树不包含这条边。
（算法导论上习题23.1-5要证明：如果一条边是一个圈中权值最大的边，一定有一棵最小生成树不包含它。由这个结论可以立刻得出。当圈中最大权值的边唯一时，算法导论上这个命题稍弱。）
至此证明了任何两棵不同的最小生成树A,B，可以随意选一条B有而A没有的边，添加到A上，由（4）的结论，形成的圈里，至少有一条边和这条新加的边权值相同,并且它不在B中，删掉它。这样可以最终把A转化成B。
 

5) 对于一个连通无向图的生成树，只考虑它的边权，形成的有序边权列表中，最小生成树是有序边权列表字典序最小的。（字典序就是通常的定义，两个序列A,B的字典序相同当且仅当A=B。否则，序列A,B出现最早位置的不相等的元素时，如果序列A的该位置元素更小，则序列A字典序小，反之，则序列B的字典序更小。如果直到一个序列结束都没有这样的位置，则较短的序列字典序小）。
 
证：设A是一棵最小生成树，而B是不是一棵最小生成树。利用(2)的结论，因为任何最小生成树的有序边权列表是相同的，所以可以用Krusal算法产生的最小生成树的有序边权列表。Krusal算法的优点是按边权顺序加边，并且当边权相等时，只要不形成圈，加哪条边都可以形成最小生成树。把B的边都按递增顺序排序：
B的边按权值递增排序后为b1, b2,……bn  w(b1)≤w(b2)≤……w(bn)
用Krusal算法求原图的一棵最小生成树，
具体地，加第i条边时(1≤i≤n),如果对该加的边e，有w(e)=w(bi),则选择bi代替e加入。不可能出现w(e)>w(bi),因为Krusal算法是按边权由小到大考虑加边的，如果出现这种情况，说明，选择bi加入是不合法的——会形成圈，而此时的图是树B的子图，这与B是树矛盾。
 
注：有了（2）的结论，结合Krusal算法的过程，知道Krusal算法加边的顺序构成的边权列表就是一个有序边权列表。于是，只考虑有序边权列表时，可以用Krusal算法产生的特殊的最小生成树代替任何一棵最小生成树。
 
如果一棵树是最小生成树，则对它采取一次（1）中的操作，显然，它的总权值不减。那么它的逆命题是不是成立？也就是如果说一棵生成树，对它采取一次（1）中的操作后，它的总权值不减，它是否是最小生成树？再换句话说，一棵非最小生成树，是否一定可以找到一条边进行（1）中的操作后，总权值会减小？这个命题看起来是显然的，但是是否有可能一棵非最小生成树当前无论怎样采取（1）中的操作都会造成总权值暂时的增大，而至少要操作两次，才能把权值降低呢？答案是不会的。
 

6) 一棵树不是最小生成树，则一定存在一个（1）中描述的操作，使得操作之后，它的总权值减小。
 
证：设A不是最小生成树，A的边按权值递增排序后为a1, a2,……an   w(a1)≤w(a2)≤……w(an)。利用Krusal算法，加第i条边时(1≤i≤n),如果对该加的边ei，有w(ei)=w(ai),则选择ai代替ei加入。直到第j次时(1≤j≤n)，有w(ej)j),则仍加入ej,自此后仍执行普通的Krusal算法（即任意处理权值相同的边），这样生成的最小生成树E，有w(ej)j) 且对所有1≤i有ei=ai，由于权值递增关系，ej不在A中，那考虑把ej加入到A中形成的圈，圈里其他任意的边ax,若w(ax)≤w(ej)j),则有x，于是这些边是在第j步之前和Krusal算法一样加入的。因此，圈里至少有一条边ay满足w(ay)≥w (aj)>w(ej) （y≥j>x）,于是删除ay可以让A的总权值减小。
 
注：可见确实有这样的操作。于是立刻得出以下结论：

7) 一棵生成树不是最小生成树，则一定存在（1）中的操作，不断进行把它转换成一棵最小生成树，而且每次操作后权树的总权值都会减小。
 
证：由（6）知，存在一个这样的操作，任选一个这样的操作，总权值会减小。这样不断地进行下去，因为不同的生成树的个数是有限的，所以总权值不可能一直减小下去，也不可能无限逼近与一个常数，最终可以使其变成一棵最小生成树。
 
注：由此可知，这种操作也是“任意”选边的，并没有特殊性。如果把一个图的所有生成树看作节点，把对每个生成树进行一次（1）中定义操作看作形成的树作为它的邻居。
那么综合上述结论：形成的图是个无向连通图。任何“局部最优解”也是“全局最优解”(只进行一次操作不能减小总权值，则是最小生成树，可以随意从任何一个“非最优点”，保持权值减小地逐步达到“最优点“)。

8)如果一棵生成树，任何边都在某棵最小生成树上，则它不一定是最小生成树。

反例：考虑一个长为2，宽为1的矩形。构造一个无向图，节点就是矩形顶点，边就是矩形的边，边权就是矩形边长。显然，原图有两棵最小生成树（“两宽与一长”），所有边都在某棵最小生成树上，但是有两棵生成树不是最小生成树（“两长与一宽”）。

内容来自：http://m.blog.csdn.net/blog/zengchenacmer/17323245