定理7.8:克鲁斯科尔算法所得到的图T是 最小生成树。 证明首先由定理71等价定义4T是无 回路图,且在T的任两个不相邻的顶点之 间添加一边恰得到一条回路)知T是G的 棵子树。 并由等价定义(2)可知边数为n-(T是无回 路图,且e=n-1),所以为G的生成树。 下面证明T是最小生成树即可
定理7.8:克鲁斯科尔算法所得到的图T是 最小生成树。 证明:首先由定理7.1等价定义(4)(T是无 回路图,且在T的任两个不相邻的顶点之 间添加一边,恰得到一条回路)知T是G的 一棵子树。 并由等价定义(2)可知边数为n-1(T是无回 路图,且e=n-1)，所以为G的生成树。 下面证明T是最小生成树即可
用反证法证明,假设T不是G的最小生成树,而S是 G的生成树,并且W(S)W(T) 在生成树T中有n-1条边。 按权从小到大的顺序排列为e12,,…,en1° 若e1是不在S中的第一条边,也就是说e1,e2, ℃k-1 是S和T的公共边。 现在对S进行变换在S上加边e得到一条回路,记 为C,在C中必有一边e∈S,但e'gT,否则T中有回 路,导致矛盾。 但因为e1e2,k1是S和T的公共边,e∈S,所以 1929℃k-1 和e不构成回路, 根据克鲁斯科尔算法知w(e)≤w(e)(否则T应选e")
用反证法证明, 假设T不是G的最小生成树,而S是 G的生成树, 并且 W(S)<W(T)。 在生成树T中有n-1条边。 按权从小到大的顺序排列为e1 ,e2 ,,ek ,,en-1。 若ek是不在S中的第一条边, 也就是说e1 ,e2 ,,ek-1 是S和T的公共边。 现在对S进行变换,在S上加边ek得到一条回路, 记 为C ,在C中必有一边e‘S, 但e’T,否则T中有回 路,导致矛盾。 但因为e1 ,e2 ,,ek-1是S和T的公共边, e‘S,所以 e1 ,e2 ,,ek-1和e’不构成回路, 根据克鲁斯科尔算法知w(ek )≤w(e')(否则T应选e')