精选最小生成树模型与实验.doc

最小生成树模型与实验
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第155页
第六章 最小生成树模型与实验
树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都树，简称为最小树。即
〔〕
式中对的所有生成树取最小。
求最小树通常用以下两种方法。
〔1〕破圈法：在给定连通图中，任取一圈，去掉一条最大权边〔如果有两条或两条以上的边都是权最大的边，那么任意去掉其中一条〕，在余图中〔是图
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第159页
的生成子图〕任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图的最小树。
例 。。
1
3
5
1
2
4
2
3
图
，；， ； ，，，；， ；，，，； ， 。
解： 取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。
，得到一棵生成树，即为所求最小树，。
〔2〕避圈法(Kruskal算法)：在连通图中，任取权值最小的一条边〔假设有两条或两条以上权相同且最小，那么任取一条〕，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图就是所求最小树。
算法的具体步骤如下：
第一步：令，〔空集〕
第二步：选一条边，且是使图中不含圈的所有边中权最小的边。如果这样的边不存在，由
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第161页
是最小树。
第三步：把换成，返回第二步。
。
2
1
1
2

解： 在中权值最小的边有，从中任取一条；在中选取权值最小的边；在中权值最小边有，，从中任取一条边；在中选取；在中选取。但与都会与已选边构成圈，故停止，。
最小生成树〔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);
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第161页
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;
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第162页
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;