络中的权最大的边去除，过程如图9-34所示。

v338394550v44260v338394550v44240v338394550v4424040v237v0v5v238v052v5v23837v038v54652374646v123v6v4424038v1v3394523v6v44240v1v3383923v6v4

v33839454240v237v04638v5v237v038v5v237v038v5v1v3383923v6v440v123v6v123v6

v237v038v5v123v6

图9-34

9.11 解： (a)用Kruskal 算法。从图中选取最小边GH=1，从未选边中选出AD=2,依次寻找下去，分别找出CG=2,GF=2,BG=3,AE=3,FE=4,以{AD,AE, FE, GF,GH,CG,BG}构成的图正好就是一颗最小支撑树，如图9-35所示。

C3(5)3(6)DE2(3)G2(4)F2(2)4(7)1(1)HAB

图9-35

用破圈法。从ABC所构成的圈中去掉最大边AB=8，从ADBC所构成的圈中去掉最大边AC=7，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-36(a)和图9-36 (b)。

37

C7(2)7(3)8(1)25(7)G2F4E36(6)C233G2F31HB4(9)37(4)1HBA2DA236(5)4(8)4ED

(a) (b)

图9-36

(b) 用Kruskal 算法。从图中选取最小边AC=1，从未选边中选出BC=2与AC=1不构成圈，再从未选边中选出CE=2。依次寻找下去，分别找出EG=2,DE=2, EF=3,以{AC,BC,CE,DE,EF,EG}构成的图正好就是一个最小支撑树，如图9-37所示。

DA1(1)2(5)2(3)2(4)G2(2)CE3(6)BF

图9-37

用破圈法。从ABC所构成的圈中去掉最大边AB=3，从ADEC所构成的圈中去掉最大边AD=4，依次进行破圈，知道所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-38(a)和图9-38(b)所示

A3(4)4(2)D22CE35(1)4(3)3(5)DA122G122BC22E3FGBF

(a) (b)

图9-38

(c) 用Kruskal 算法。从图中选取最小边DE=1，从未选边中选出AB=2与DE=1不构成圈，从未选边中选出AC=2,依次寻找下去，分别找出BD=2,HJ=2,IJ=2,FH=2,GI=3,DF=3,以{AC,AB,BD,DE,DF,FH,HJ,IJ,GI}构成的图正好就是一个最小支撑树，如图9-39所示。

38

B2(4)2(2)HD3(9)F2(7)2(5)A2(3)1(1)JEG2(8)2(6)

图9-39

用破圈法。从BDFH所构成的圈中去掉最大边BH=5，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-40(a)和图9-40(b)。

B2A2C3(4)2(7)5(1)HF3(6)BH21D3F22JEG2I221D324(3)2J2IA23(5)E5(2)G22C

(a) (b)

图9-40

(d) 用Kruskal 算法。从图中选取最小边EF=1，从未选边中选取DF=2与EF=1不构成圈，再从未选边中选出CG=3，依次寻找下去，分别找出AB=3, CD=4, BC=4,

以{AB,BC,CD,CG,DF,EF}构成的图正好就是一个最小支撑树，如图9-41 所示。

AD4(5)3(4)4(6)2(2)1(1)FEC3(3)BG图9-41

用破圈法。从BCG所构成的圈中去掉最大边BG=7，从CEG所构成的圈中去掉最大边EG=6，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-42(a)和图9-42(b)

39

A35(4)6(3)D4C7(1)23(6)5(5)F1EA34D4C21E3F4B

36(2)GBG

(a) (b)

图9-42

9.12 解: 用Kruskal 算法。从图中选取最小边CD=1,EF=1，从未选边中选取EF=1与CD不构成圈，再从未选边中选出AB=2,BC=2,CE=3,FG=4,以{AB,BC,CD,CE,EF,FG}构成的图正好就是一颗最小支撑树，如图9-43(a)所示。

B2(3)2(4)A1(1)F4(6)GC3(5)1(2)DE图9-43

用破圈法。从EFG所构成的圈中去掉最大边EG=7，从BCF所构成的圈中去掉最大边BF=7，依次进行破圈，直到所有边构成的图中不含有圈为止。破圈过程和最小支撑树见图9-44(a)和图9-44(b)

B225(3)1B7(2)4(4)A4(5)FG47(1)22C34(6)AF41GC131DEDE

(a) (b)

图9-44

9.13 解：把题中表用图的形式表示出来，如图9-45(a)所示。用Kruskal 算法。从图中选取最小边CD=2，从未选边中选取AE=13，与CD不构成圈，再从未选边中选出BF=20，BD=34，AD=50，以{AE,AD,CD,BD,BF}构成的图正好就是一个最小支撑树，如图9-45(c)所示。

40