支撑树与最小支撑树习题解答 10.3 解 （1）破圈法
根据破圈法的基本原理，去掉（在边上用“/”表示） ① 取圈（v 1，v 2，v 3），去掉边e 2 ② 取圈（v 1，v 2，v 5），去掉边e 7 ③ 取圈（v 2，v 3，v 4），去掉边e 3 ④ 取圈（v 2，v 4，v 5），去掉边e 5 ⑤ 取圈（v 4，v 5，v 6），去掉边e 10 ⑥ 取圈（v 8，v 9，v 10），去掉边e
14
得到一个支撑树如图
10-7
（2）避圈法
①任取一条边e 1，找一条与e 1不构成圈的边e 4 ②找一条与{e 1, e 4}不构成圈的边e 6 ③找一条与{e 1, e 4，e 6}不构成圈的边e 8 ④找一条与{e 1, e 4，e 6, e 8}不构成圈的边e 9
⑤找一条与{e 1, e 4，e 6, e 8, e 9}不构成圈的边e 11 ⑥找一条与{e 1, e 4，e 6, e 8, e 9, e 11}不构成圈的边e 12 ⑦ 找一条与{e 1, e 4，e 6, e 8, e 9, e 11, e 12}不构成圈的边e 15 ⑧ 找一条与{e 1, e 4，e 6, e 8, e 9, e 11, e 12，e 15}不构成圈的边e 14 ⑨ 得到一个支撑树{e 1, e 4，e 6, e 8, e 9, e 11, e 12，e 15，e 14}。 ⑩
如图10-8所示
10.4 解 解（a ）给图中的点和边分别加上名称，如图
10-10
（1） 避圈法的方法为：开始选一条最小权的边，以后每步中，总从未被选取的边上选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条。
i 表示第i 次的选取。 e 13 e 15
e 3 e 9 e 10 e 5 e 17
②⑥⑥ 1 1 2 2 3 3 4
图10-11
则以{e 13, e 15，e 3, e 9, e 10, e 5, e 17}构成的图正好就是一个支撑树 支撑树的权为：
1+1+2+2+3+3+4=16
对应的最小树如图10-12所示
（2） 破圈法的基本方法是：任取一个圈，从圈中去掉一条权最大的边。（如果两条或两条以上的边都是权最大的边，则去掉任意一条），在余下的图中，重复
按照上述方法，去边的具体过程如图10-13所示。i 次进行删除的边。
得到最小树如图10-14所示。
（b ）给（b ）中的点和边加上名称分别为v i ，e i ，如图10-15所示
（Ⅰ）避圈法：依次找不构成圈的最小边，寻找过程如图10-16所示
则由{e 3, e 4，e 5, e 9, e 8, e 2}构成最小支撑树，如图
10-17
树的权重为：
1+1+2+2+3+2=11
(Ⅱ) 破圈法：本质为依次从所构成的圈中去除最大边，去除过程如图10-18所示
最后剩下的边{e 2, e 3, e 4，e 5, e 8, e 9}所构成的图为最小支撑树 总权重为：
1+1+2+2+2+3=11
（c ）给（c ）中的点和边加上名称分别为v i ，e i ，如图10-19所示
（Ⅰ）避圈法：寻找最小边的过程如图10-20所示
则由{e 6, e 5，e 2, e 4, e 8, e 9，e 10, e 11, e 15}构成最小支撑树，如图
10-21
树的权重为1+2+2+2+3+3+2+2+2=19 (Ⅱ) 破圈法：去除过程如图10-22所示
最后剩下的边{e 1, e 2，e 5, e 6, e 8, e 9，e 10, e 11, e 15}所构成的图为最小支撑树 如图10-23所示
总权重为：
2+2+2+3+1+2+3+2+2=19
（d ）给（d ）中的点和边加上名称分别为v i ，e i ，如图10-24所示
（Ⅰ）避圈法：寻找最小边的过程如图10-25所示
最后找出{e 7, e 6，e 1, e 8, e 2，e 10}构成最小支撑树，如图
10-26
总权重为：
w (T )=3+4+4+2+1+3=17
(Ⅱ) 破圈法：去除图中最大边的过程如图10-27所示
最后剩下的边{e 1, e 2，e 10, e 6, e 7, e 8}所构成的图为最小支撑树 如图10-28所示
总权重为：
w (T )=3+4+4+2+1+3=17 10.5 解 把题设中的表用图表示如下：
采用避圈法，寻找最小边的过程如图10-30所示
最后找到{[L , p a ], [P l , T ], [P l , L ], [L , N ], [N , M ]}构成最小支撑树，如图10-31所示
总权重为：
w (T )=2+13+50+34+20=119
支撑树与最小支撑树习题解答 10.3 解 （1）破圈法
根据破圈法的基本原理，去掉（在边上用“/”表示） ① 取圈（v 1，v 2，v 3），去掉边e 2 ② 取圈（v 1，v 2，v 5），去掉边e 7 ③ 取圈（v 2，v 3，v 4），去掉边e 3 ④ 取圈（v 2，v 4，v 5），去掉边e 5 ⑤ 取圈（v 4，v 5，v 6），去掉边e 10 ⑥ 取圈（v 8，v 9，v 10），去掉边e
14
得到一个支撑树如图
10-7
（2）避圈法
①任取一条边e 1，找一条与e 1不构成圈的边e 4 ②找一条与{e 1, e 4}不构成圈的边e 6 ③找一条与{e 1, e 4，e 6}不构成圈的边e 8 ④找一条与{e 1, e 4，e 6, e 8}不构成圈的边e 9
⑤找一条与{e 1, e 4，e 6, e 8, e 9}不构成圈的边e 11 ⑥找一条与{e 1, e 4，e 6, e 8, e 9, e 11}不构成圈的边e 12 ⑦ 找一条与{e 1, e 4，e 6, e 8, e 9, e 11, e 12}不构成圈的边e 15 ⑧ 找一条与{e 1, e 4，e 6, e 8, e 9, e 11, e 12，e 15}不构成圈的边e 14 ⑨ 得到一个支撑树{e 1, e 4，e 6, e 8, e 9, e 11, e 12，e 15，e 14}。 ⑩
如图10-8所示
10.4 解 解（a ）给图中的点和边分别加上名称，如图
10-10
（1） 避圈法的方法为：开始选一条最小权的边，以后每步中，总从未被选取的边上选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条。
i 表示第i 次的选取。 e 13 e 15
e 3 e 9 e 10 e 5 e 17
②⑥⑥ 1 1 2 2 3 3 4
图10-11
则以{e 13, e 15，e 3, e 9, e 10, e 5, e 17}构成的图正好就是一个支撑树 支撑树的权为：
1+1+2+2+3+3+4=16
对应的最小树如图10-12所示
（2） 破圈法的基本方法是：任取一个圈，从圈中去掉一条权最大的边。（如果两条或两条以上的边都是权最大的边，则去掉任意一条），在余下的图中，重复
按照上述方法，去边的具体过程如图10-13所示。i 次进行删除的边。
得到最小树如图10-14所示。
（b ）给（b ）中的点和边加上名称分别为v i ，e i ，如图10-15所示
（Ⅰ）避圈法：依次找不构成圈的最小边，寻找过程如图10-16所示
则由{e 3, e 4，e 5, e 9, e 8, e 2}构成最小支撑树，如图
10-17
树的权重为：
1+1+2+2+3+2=11
(Ⅱ) 破圈法：本质为依次从所构成的圈中去除最大边，去除过程如图10-18所示
最后剩下的边{e 2, e 3, e 4，e 5, e 8, e 9}所构成的图为最小支撑树 总权重为：
1+1+2+2+2+3=11
（c ）给（c ）中的点和边加上名称分别为v i ，e i ，如图10-19所示
（Ⅰ）避圈法：寻找最小边的过程如图10-20所示
则由{e 6, e 5，e 2, e 4, e 8, e 9，e 10, e 11, e 15}构成最小支撑树，如图
10-21
树的权重为1+2+2+2+3+3+2+2+2=19 (Ⅱ) 破圈法：去除过程如图10-22所示
最后剩下的边{e 1, e 2，e 5, e 6, e 8, e 9，e 10, e 11, e 15}所构成的图为最小支撑树 如图10-23所示
总权重为：
2+2+2+3+1+2+3+2+2=19
（d ）给（d ）中的点和边加上名称分别为v i ，e i ，如图10-24所示
（Ⅰ）避圈法：寻找最小边的过程如图10-25所示
最后找出{e 7, e 6，e 1, e 8, e 2，e 10}构成最小支撑树，如图
10-26
总权重为：
w (T )=3+4+4+2+1+3=17
(Ⅱ) 破圈法：去除图中最大边的过程如图10-27所示
最后剩下的边{e 1, e 2，e 10, e 6, e 7, e 8}所构成的图为最小支撑树 如图10-28所示
总权重为：
w (T )=3+4+4+2+1+3=17 10.5 解 把题设中的表用图表示如下：
采用避圈法，寻找最小边的过程如图10-30所示
最后找到{[L , p a ], [P l , T ], [P l , L ], [L , N ], [N , M ]}构成最小支撑树，如图10-31所示
总权重为：
w (T )=2+13+50+34+20=119