解：过程如下： 3 5
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 解：过程如下： 1 v5 v8 2 1 v1 v5 v8 2 3 1 v1 v4 v5 v8 3 v7 2 1 5 v1 v4 v5 v8 3 v7 2 1 5 6 v1 v4 v5 v8 v3
3 9 V> 2、算法证明 定理1由克鲁斯克尔算法得到的任何生成树一定是最小 生成树。 证明：设G是一个n阶连通赋权图，用T*=G(e1,e2,em1}]表 示由克鲁斯克尔算法得到的一棵生成树，我们证明：它是最小 生成树
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 3 v7 2 1 5 6 v1 v4 v5 v8 v3 v6 8 3 v7 2 1 5 6 v1 v4 v5 v8 v3 v6 8 v2 9 2、算法证明 定理1 由克鲁斯克尔算法得到的任何生成树一定是最小 生成树。 证明：设G是一个n阶连通赋权图，用T*=G[｛e1 ,e2 ,.,en-1｝]表 示由克鲁斯克尔算法得到的一棵生成树，我们证明：它是最小 生成树
设T是G的一棵最小生成树。若T*≠T. 由克鲁斯克尔算法容易知道：T∩T*Φ。 于是令fT)=k表示T*中的边e不在T中的最小i值。 即可令T=G{e1,e2,ek1,ek,e'm}] 考虑：TUek,则由树的性质，它必然为G中圈C。 设e是圈C的在T中，但不在T*中的边。 作T,=TUek-e,容易知道：T还为G的一棵生成树。 由克鲁斯克尔算法知道： w(e)≥w(ek) 所以：w(T)≥w(G) 这说明T,是最小树，但这与T)的选取假设矛盾！所 以：T=T*
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 设T是G的一棵最小生成树。若T*≠T. 由克鲁斯克尔算法容易知道：T∩T*≠Φ。 于是令f (T)= k 表示T*中的边ei不在T中的最小i值。 即 可令 T=G[｛e1 ,e2 ,.,ek-1 , e' k ,.,e' n-1｝] 考虑：T∪ek ,则由树的性质，它必然为G中圈C。 作 T1= T ∪ek- e ,容易知道：T1还为G的一棵生成树。 设e是圈C的在T中，但不在T*中的边。 由克鲁斯克尔算法知道： ( ) ( ) w e w e k 所以： 1 w T w T ( ) ( ) 这说明T1是最小树，但这与f(T)的选取假设矛盾！所 以：T = T*
例2在一个边赋权G中，下面算法是否可以产生有最小 权值的生成路？为什么？ 算法：(1)选一条边e使得w(e)尽可能小； (2)若边e1,e2,e已经选定，则用下述方法从E(e1,e,)中 选取边e+1 (a)GL{e1e2,e,e+1}]为不相交路之并； (b)w(e+)是满足(a)的尽可能小的权。 (3)当(2)不能继续执行时停止。 解：该方法不能得到一条最小生成路
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 例2 在一个边赋权G中，下面算法是否可以产生有最小 权值的生成路？为什么？ 算法: (1) 选一条边e1 ,使得w(e1 )尽可能小； (2) 若边e1 ,e2 ,.,ei已经选定，则用下述方法从E\｛e1 ,.,ei｝中 选取边ei+1： (a) G[｛ e1 ,e2 ,.,ei ,ei+1｝]为不相交路之并； (b) w(ei+1)是满足(a)的尽可能小的权。 (3)当 (2)不能继续执行时停止。 解：该方法不能得到一条最小生成路
例如，在下图G中我们用算法求生成路： 用算法求出的生成路为： 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 例如，在下图G中我们用算法求生成路： 3 1 2 2 3 4 3 6 6 7 9 10 用算法求出的生成路为： 1 2 2 6 9 3