最小生成树模型与实验.docx

第六章最小生成树模型与实验
树是图论中的一个重要概念，由于树的模型简单而实用，它在企
业管理、线路设计等方面都有很重要的应用。
§
上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使 用实例来说明。

(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一 条)，在余图中(是图弓的生成子图)任取一圈，去掉一条最大权边， 重复下去，直到余图中无圈为止，即可得到图G的最小树。
例 。。
,=匡，v2]，w(q) = 1 ； e2 =[。，七], w(e2) = 4 ；

e3 = [v2,v3], w(e3) = 2 , e4 = [v2,v4], w(e4) = 3 ； e5 = [v3,v4]， w(e5) = 1 ； e6 = [v2,v5], w(e2) = 5 , e7 = [v4,v5], w(e7) = 2 ； e8 = [v2,v5], w(e8) = 3。
解：
^>^-圈｛vevevev ｝ 掉 e ；取^-圈｛vevevev ｝ 掉 e ；
112332 1 2 265833 2 6
取一圈｛ve vevcvc｝去掉e^ ；取一圈｛v e^ve^v^e^vA｝去掉e^。
1244533 2」 8 475835 4」 8
，得到一棵生成树，即为所求最小树广*,
w(T *) = 1 + 2 +1 + 2 = 6。
(2)避圈法(Kruskal算法)：在连通图G中，任取权值最小的一 条边(若有两条或两条以上权相同且最小，则任取一条)，在未选边 中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去， 直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图广就 是所求最小树。
算法的具体步骤如下：
第一步：令i = 1, e0m (空集)
第二步：选一条边e, G E \ E.,且°‘是使图G. = (V, %] u {E})中不含 圈的所有边e(e w E \ E.)中权最小的边。如果这样的边不存在，由 T = (V, E. _1)是最小树。
第三步：把i换成,+ 1,返回第二步。
。
解： 在le e A e ｝中权值最小的边有e e，从中任取一条e ；在
e，eo， ，e e，e e
12 8 15 1

｛e2,e3,A ,e8｝中选取权值最小的边e5 ； 在｛e2,e2,A ,e8｝中权值最小边有e3 , e7 , 从中任取一条边e3 ；在｛e2,e4,e6,e7,e8｝ 中选取e7 ；在｛e2,e4,e6,e8｝中选取
e4, e8。但e4与e8都会与已选边构成圈，
故停止， 一样的结果。
最小生成树（minimal spanning tree , ]^。模型概括为：给定
网络中一些点和这些点之间的距离，寻找连接所有这些点的最小总距 离。
使用LINGO软件编制此题的程序如下：
MODEL:
!Given the number of nodes and the distance between them, finding the shortest total distance of links on the network to connect all the nodes is the classic problem called minimal spanning tree (MST);
SETS:
CITY / 1.. 5/: U; ! U( I) = level of city I;
! U( 1) = 0;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X;
! X(
I, J)
=1
if we use link I, J;
ENDSETS
DATA:
! Distance
matrix need not be
symmetric;
! However,
city
1 is
base of the tree;
!to:
A
B
C
D
E;
DIST =
0
1
3
4
6 !from
A;
1
0
2
3
5 !from
B;
3
2
0
1
3 !from
C;
4
3
1
0
2 !from
D;
6
5
3
2
0;!from
E;
ENDDATA
! The model size: Warning, may be slow