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

第六章 最小生成树模型与实验
树是图论中的一个重要概念，由于树的模型简单而实用，它在企 业管理、线路设计等方面都有很重要的应用。
§ 树与树的性质 上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使 用实例来说明。
图 6大权边, 重复下去，直到余图中无圈为止，即可得到图G的最小树。
例 用破圈法求图 的最小树。图 是一赋权图。
v
5
v
图
= ［v1，v2］，w(e1)= 1 ； e2 二 M，v3］， 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。
解：取一圈｛v1e1v2e3v3e2vj 去掉e2 ;取一圈｛v2e6v5e8v3e3v2｝去掉e6 ；
取一圈｛v2e4v4e5v3e3v2｝去掉e8 ;取一圈｛v4e7v5e8v3e5v4｝去掉e8。
，得到一棵生成树，即为所求最小树t*，
w(T*) = 1 + 2 +1 + 2 = 6。
避圈法(Kruskal算法)：在连通图g中，任取权值最小的一条 边(若有两条或两条以上权相同且最小，则任取一条)，在未选边中 选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直 到不存在与已选边不构成圈的边为止。已选边与顶点构成的图t就是 所求最小树。
算法的具体步骤如下：
第一步：令i = 1， E0=Q (空集)
第二步：选一条边e. e E \ E.，. = (V, E 1 u{E})中不含
III i I—1
圈的所有边e(e e E\ E.)中权最小的边。如果这样的边不存在，由
T = (V,E ) 是最小树。
i —1
第三步：把i换成i +1，返回第二步。
例 用避圈法求图 的最小树。
解：在｛e1,e2，…,e8｝中权值最小的边有q,e5，从中任取一条e 1 ； 在
1 2 8 1 5 1
v5
图
｛e2, e3，…,e8｝中选取权值最小的边e5 ；
2 3 8 5
在｛e2,e2,…,e8｝中权值最小边有e3，e7， 从中任取一条边e3 ； 在｛e2,e4,e6,e7,e8｝ 中选取e7 ； 在｛e2,e4,e6,e8｝中选取 e ,e°。但e4与e°都会与已选边构成圈,
4 8 4 8
故停止，得到与图 一样的结果。
最小生成树(minimal spanning tree , MST )模型概括为：给定网
络中一些点和这些点之间的距离，寻找连接所有这些点的最小总距
离。
使用 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;
ENDSETS
X;
! X( I, J) = 1
if we use link I, J;
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 for N >= 8; N = ***@SIZE( CITY);
! Minimize total distance of the links;
MI