例1今要在七个城市之间修筑一个公路网，每两个城 市之间的公路修筑费用就是各条边上的权，见图7-11。试 二求总修筑费用最小的公路网。 V 3V5 2 03 4 10 5 5 6 图7-11 01 图7-12 解：(I)破圈法：从圈{v,,w,}中去掉边[，小；从 圈{V}中去掉边[6,小从圈{}中去掉边 [y,:从圈{2}中去掉边[，v;从圈{vV} 中去掉边[v1,]:从圈{v}中去掉边[v4,,得最小 树T*如图7-12，其总权数为0（T*)=2+3+4+3+4+5=21. (2)避圈法：依次选取边[v4,v],[,小，[1，vd, [v5,V6d, 二[v2,v小， [2,],画出这棵最小树仍同图7-12。 例1 今要在七个城市之间修筑一个公路网，每两个城 市之间的公路修筑费用就是各条边上的权，见图7-11。试 求总修筑费用最小的公路网。 v2 v4 v5 v6 v1 v3 v7 图7-11 10 8 3 4 3 4 5 5 2 7 6 6 解：⑴破圈法：从圈｛v1v6v7v1｝中去掉边[v1 ,v7 ]；从 圈｛v5v6v7v5｝中去掉边[v6 ,v7 ]；从圈｛v3v4v6v3｝中去掉边 [v3 ,v4 ]；从圈｛v2v3v6v2｝中去掉边[v3 ,v6 ]；从圈｛v1v2v6v1｝ 中去掉边[v1 ,v2 ]；从圈｛v4v5v6v4｝中去掉边[v4 ,v6 ]，得最小 树T﹡如图7-12，其总权数为ω（T﹡）=2+3+4+3+4+5=21。 ⑵避圈法：依次选取边[v4 ,v5 ]， [v5 ,v7 ]， [v1 ,v6 ]，[v5 ,v6 ]， [v2 ,v6 ]， [v2 ,v3 ]，画出这棵最小树仍同图7-12。 v7 v5 v4 v6 v1 v2 v3 图7-12 3 3 4 4 2 5