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

第六章 最小生成树模型与实验

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

图 6.1
例6.1 已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。
用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。

定义6.1 一个无圈的连通图称为树.

例6.2 某大学的组织机构如下所示:
文科办公室
教务处
研究处
理科办公室
校行政办公室 研究生院
财务科
数学系
校长
行政科
物理系
理工学院
校教学办公室
人事学院
外语学院
……
如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。
树的性质：
（1） 树必连通，但无回路（圈）；
（2） 个顶点的树必有条边；
（3） 树中任意两点间，恰有一条初等链；
（4） 树连通，但去掉任一条边，必变为不连通；
（5） 树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。
生成树与最小树
定义6.2 设图是图的生成子图，如果是一棵树，记，则称是的一棵生成树。
定理6.1 图有生成树的充分必要条件是图的连通的。
证：必要性是显然的
充分性：设是连通图。
（i）如果不含圈，由定义6.1可知，本身就是一棵树，从而是它自身的生成树。
（i i）如果含圈，任取一圈，从圈中任意去掉一条边，得到图的一个生成子图，如果不含圈，那么是的一棵生成树（因为易见是连通的）；如果仍含少量圈，那么从中任取一个圈，从圈中再任意去掉一条边，得到图的一个生成子图，如此重复，最终可以得到的一个生成子图，它不含圈，则是图的一棵生成树。
§6.2 最小生成树的实例与求解

1

图 6.2

e7
由以上充分性的证明中，提供了一个寻求连通图的生成树的方法，称这种方法为“破圈法”。
例6.4 在图6.1中，用破圈法求出图的一棵生成树
解： 取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉；
如图6.3所示，此图是图6.2的一个生成子图，且为一棵树（无圈），所以我们找一棵生成树，其中，。
不难发现，图的生成树不是唯一的，对于上例若这样做：
取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。

图6.3 图6.4
如图的生成树还有另外一种方法“避圈法”，主要步骤是在图中任取一条边，找出一条不与构成圈的边，再找出不与构成圈的边。一般地，设已有，找出一条不与构成圈的边，重复这个过程，直到不能进行下去为止。这时，由所有取出的边所构成的图是图的一棵生成树。
定义6.2 设是赋权图的一棵生成树，称中全部边上的权数之和为生成树的权，记为。即
。 (7.1)
如果生成树的权是的所有生成树的权中最小者，则称是的最小生成树，简称为最小树。即
（7.2）
式中对的所有生成树取最小。
求最小树通常用以下两种方法。
（1）破圈法：在给定连通图中，任取一圈，去掉一条最大权边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条），在余图中（是图的生成子图）任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图的最小树。
例 6.4 用破圈法求图6.5的最小树。图6.5是一赋权图。
1

3
5
1
2
4
2
3
图 6.5
，；， ； ，，，；， ；，，，； ， 。
解： 取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。
如图6.6所示，得到一棵生成树，即为所求最小树，。
（2）避圈法(Kruskal算法)：在连通图中，任取权值最小的一条边（若有两条或两条以上权相同且最小，则任取一条），在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图就是所求最小树。
算法的具体步骤如下：
第一步：令，（空集）
第二步：选一条边，且是使图中不含圈的所有边中权最小的边。如果这样的边不存在，由是最小树。
第三步：把换成，返回第二步。
例6.5 用避圈法求图6.5的最小树。

2

1
1
2
图6.6
解： 在中权值最小的边有，从中任取一条；在中选取权值最小的边；在中权值最小边有，，从中任取一条边；在中选取；在中选取。但与都会与已选边构成圈，故停止，得到与图6.6一样的结果。
最小生成树（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;
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 for N >= 8;
N = @SIZE( CITY);
! Minimize total distance of the links;
MIN = @SUM( LINK: DIST * X);

! For city K, except the base, ... ;
@FOR( CITY( K)| K #GT# 1:

! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;

! If there are 2 disjoint tours from 1 city to
another, we can remove a link without breaking
connections. Note: These are not very powerful
for large problems;
@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K); );
);

! There must be an arc out of city 1;
@SUM( CITY( J)| J #GT# 1: X( 1, J)) >= 1;

! Make the X's 0/1;
@FOR( LINK: @BIN( X); );

! The level of a city except the base is at least
1 but no more than N-1, and is 1 if it links to
the base;
@FOR( CITY( K)| K #GT# 1:
@BND( 1, U( K), 999999);
U( K) <= N - 1 - ( N - 2) * X( 1, K); );
END
使用Solve求解获得如下结果：
得到与图6.6一样的结果, X(1,2)=1, X(2,3)=1, X(3,4)=1,X(4,5)=1, 其它
X(I,J)=0。最优值。
§6.3 最小生成树的应用与LINGO软件求解
使用最小生成树程序应用求解下面具体例子。
例6 已知五个城市Atlanta, Chicago, Cincinnati, Houston 和 LA其距离矩阵如表6.1所示。 求解连接五个城市网络的最小生成树。
表6.1
距离
km

ATL
CHI
CIN
HOU

LA
ATL
0
702
454
842
2396
CHI
702
0
324
1093
2136
CIN
454
324
0
1137
2180
HOU
842
1093
1137
0
1616
LA
2396
2136
2108
1616
0

使用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).

This model finds the (MST) connecting Atlanta,
Chicago, Cincinnati, Houston, and LA so
that messages can be sent from Atlanta (base) to
other cities through the network at minimum cost;

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: Atl Chi Cin Hou LA ;
DIST = 0 702 454 842 2396 !from Atl;
702 0 324 1093 2136 !from Chi;
454 324 0 1137 2180 !from Cin;
842 1093 1137 0 1616 !from Hou;
2396 2136 2180 1616 0; !from LA;
ENDDATA
! The model size: Warning, may be slow for N >= 8;
N = @SIZE( CITY);

! Minimize total distance of the links;
MIN = @SUM( LINK: DIST * X);

! For city K, except the base, ... ;
@FOR( CITY( K)| K #GT# 1:

! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;

! If there are 2 disjoint tours from 1 city to
another, we can remove a link without breaking
connections. Note: These are not very powerful
for large problems;
@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K); );
);

! There must be an arc out of city 1;
@SUM( CITY( J)| J #GT# 1: X( 1, J)) >= 1;

! Make the X's 0/1;
@FOR( LINK: @BIN( X); );

! The level of a city except the base is at least
1 but no more than N-1, and is 1 if it links to
the base;
@FOR( CITY( K)| K #GT# 1:
@BND( 1, U( K), 999999);
U( K) <= N - 1 - ( N - 2) * X( 1, K); );
END
使用Solve求解获得如下结果：（省略表6.1中的城市间距离数据）。
最优解 X(1,3)=1, X(1,4)=1, X(3,2)=1, X(4,5)=1, 其它X(I,J)=0。
即：连接五个城市最小的生成树网络为：Chicago→Houston→Atlanta→Cincinnati→LA。其最小网络距离。最优值公里。
§6.4 选址问题

选址问题是指为一个或几个服务设施在一定区域内选定它的位置，使某一指标达到最优值。选址问题的数学模型依赖于设施可能的区域和评判位置优劣的标准，有许多不同类型的选址问题。在此只简单介绍服务设施与服务对象都位于一个图的顶点上的单服务设施问题。
中心问题
有些公共服务设施(例如一些紧急服务型设施如急救中心、消防站)的选址，要求网络中最远的被服务点离服务设施的距离尽可能小。
例6.7 某城市要建立一个消防站，为该市所属的七个区服务（图6.7），问应设在哪个区，才能使它至最远区的路径最短。
算法：设各顶点为Vi, i=
（1） 用最短路算法求出距离矩阵
（2） 计算在各点设立服务设施的最大服务距离

（3） 求出顶点，使，则就是要求的建立消防站的地点。此点称为图的中心点。
重心问题
有些设施（例如一些非紧急型的公共服务设施，如邮局、学校等）的选址，要求设施到所有服务对象点的距离总和最小。一般要考虑人口密度问题，要使全体被服务对象来往的平均路程最短。
例6.8某矿区有七个矿点（图6.8）。已知各矿点每天的产矿量（标在图6.8的各顶点上）。现有从这七个矿点选一个来建造矿厂。问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（单位：千吨/km）最小。
算法：顶点为Vi, i=，
（1） 求距离阵；
（2） 计算各顶点作为选矿厂的总运力：

（3） 求，使，则就是选矿厂应设之矿点。此点称为图 的重心或中位点。
例 6.9（设备更新问题） 企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用，这需支付一定的维修费用。现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少。
已知该种设备在每年年初的价格为：
第一年
第二年
第三年
第四年
第五年
11
11
12
12
13
使用不同时间设备所需维修费为：
使用年限
0-1
1-2
2-3
3-4
4-5
维修费
5
6
8
11
18
对此问题，构造加权有向图，如图6.9所示。

图6.9
的含义为：
（1） 顶点集，每个顶点代表年初的一种决策，其中顶点代表第年初购置新设备的决策，顶点代表第年初修理用过年的旧设备的决策.
（2） 弧集

　　若第年初作了决策后,第+1年初可以作决策，则顶点与之间有弧，其权代表第年初到的+1年初之间的费用.例如，弧代表第三年初买新设备，第四年初决定用第三年买的用过一年的旧设备，其权则为第三年初的购置费与三、四年的维修费之和，即12+5=17。
（3） 问题转化为顶点到的最短路问题。五年的最优购置费为

其中为顶点到的最短路的权。求得最短路的权为53。而两条最短路分别为

因此，计划为第一、三年初购置新设备，或第一、四年初购置新设备，五年费用均最省，为53。
习题六
6.1 分别用破圈法和避圈法求下面各图的最小生成树并使用LINGO求解其结果。

a) (b)

(c) (d)