Theorem 4.12 Kruskal Algorithm produces a minimum spanning tree in a connected weighted graph 证明要点： 1,假设算法得到的T不是最小生成树，找一个最小生成树T',尝试发现 矛盾； 2,这个T'有其特殊性：将T的边按权不减序（也是算法选择的序）排好， 将所有最小生成树也按边权不减序排列，取和T中e1,e2,,ek相同的树中 k最大的最小生成树T'; 3,ek+1是在T中但不在T'中的最小边； 4,针对ek+1,必定存在T'中的边e,交换ek+1和e',得到新树T”。按照算 法，w(e)>=w(ek+. 5,w(T")=w(T)-w(e')+w(ek+1).T”也是最小生成树。但同时， 因T'最小，所以，w(e)=w(ek+). 6,T”的前k+1条边和T相同。矛盾。Theorem 4.12 Kruskal Algorithm produces a minimum spanning tree in a connected weighted graph. 证明要点： 1,假设算法得到的T不是最小生成树，找一个最小生成树T’，尝试发现 矛盾； 2,这个T’有其特殊性：将T的边按权不减序(也是算法选择的序)排好， 将所有最小生成树也按边权不减序排列，取和T中e1 ,e2 ,…,ek相同的树中 k最大的最小生成树T’; 3,ek+1是在T中但不在T’中的最小边； 4,针对ek+1，必定存在T’中的边e’,交换ek+1和e’，得到新树T’’。按照算 法，w(e’)>=w(ek+1). 5, w(T’’)=w(T’)-w(e’)+w(ek+1). T’’也是最小生成树。但同时， 因T’最小，所以，w(e’)=w(ek+1). 6,T’’的前k+1条边和T相同。矛盾