支撑树与最小支撑树习题解答.docx

支撑树与最小支撑树习题解答支撑树与最小支撑树习题解答 10.3 解 破圈法 根据破圈法的基本原理，去掉 取圈，去掉边e2 取圈，去掉边e7 取圈，去掉边e3 取圈，去掉边e5 取圈，去掉边e10 取圈，去掉边e14 得到一个支撑树如图10-7 避圈法 任取一条边e1，找一条与e1不构成圈的边e4 找一条与e1,e4不构成圈的边e6 找一条与e1,e4，e6不构成圈的边e8 找一条与e1,e4，e6,e8不构成圈的边e9 找一条与e1,e4，e6,e8,e9不构成圈的边e11 找一条与e1,e4，e6,e8,e9,e11不构成圈的边e12 找一条与e1,e4，e6,e8,e9,e11,e12不构成圈的边e15 找一条与e1,e4，e6,e8,e9,e11,e12，e15不构成圈的边e14 得到一个支撑树e1,e4，e6,e8,e9,e11,e12，e15，e14。 如图10-8所示 10.4 解 解给图中的点和边分别加上名称，如图10-10 避圈法的方法为：开始选一条最小权的边，以后每步中，总从未被选取的边上选一条权最小的边，并使之与已选取的边不构成圈。 按照此方法，算法步骤如下，i 表示第i次的选取。 e13 e15 e3 e9 e10 e5 e17 1 1 2 2 3 3 4 图10-11 则以e13,e15，e3,e9,e10,e5,e17构成的图正好就是一个支撑树 支撑树的权为： 1+1+2+2+3+3+4=16 对应的最小树如图10-12所示 破圈法的基本方法是：任取一个圈，从圈中去掉一条权最大的边。，在余下的图中，重复这个步骤，一直得到一个不含圈的图为止，这时的图便是最小树。 按照上述方法，去边的具体过程如图10-13所示。其中i表示第i次进行删除的边。 得到最小树如图10-14所示。 给中的点和边加上名称分别为vi，ei，如图10-15所示 避圈法：依次找不构成圈的最小边，寻找过程如图10-16所示 则由e3,e4，e5,e9,e8,e2构成最小支撑树，如图10-17 树的权重为： 1+1+2+2+3+2=11 ()破圈法：本质为依次从所构成的圈中去除最大边，去除过程如图10-18所示 最后剩下的边e2,e3,e4，e5,e8,e9所构成的图为最小支撑树 总权重为： 1+1+2+2+2+3=11 给中的点和边加上名称分别为vi，ei，如图10-19所示 避圈法：寻找最小边的过程如图10-20所示 则由e6,e5，e2,e4,e8,e9，e10,e11,e15构成最小支撑树，如图10-21 树的权重为1+2+2+2+3+3+2+2+2=19 ()破圈法：去除过程如图10-22所示 最后剩下的边e1,e2，e5,e6,e8,e9，e10,e11,e15所构成的图为最小支撑树 如图10-23所示 总权重为： 2+2+2+3+1+2+3+2+2=19 给中的点和边加上名称分别为vi，ei，如图10-24所示 避圈法：寻找最小边的过程如图10-25所示 最后找出e7,e6，e1,e8,e2，e10构成最小支撑树，如图10-26 总权重为： w(T)=3+4+4+2+1+3=17 ()破圈法：去除图中最大边的过程如图10-27所示 最后剩下的边e1,e2，e10,e6,e7,e8所构成的图为最小支撑树 如图10-28所示 总权重为： w(T)=3+4+4+2+1+3=17 10.5 解 把题设中的表用图表示如下： 采用避圈法，寻找最小边的过程如图10-30所示 最后找到L,pa,Pl,T,Pl,L,L,N,N,M构成最小支撑树，如图10-31所示 总权重为： w(T)=2+13+50+34+20=119