09第9章--图论模型.docx

第9章 图论模型
图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。
图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（D. Kӧnig）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。
9.1 图的基础理论
9.1.1 图的基本概念
所谓图，概括地讲就是由一些点和这些点之间的连线组成的。定义为，是顶点的非空有限集合，称为顶点集。是边的集合，称为边集。边一般用表示，其中属于顶点集。
以下用表示图中顶点的个数，表示边的条数。
如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为 ，，.

图9.1 图的示意图
1.无向图和有向图
如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。如图9.1 (a)和(b)都是无向图。连接两顶点和的无向边记为或。
如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。连接两顶点和的弧记为，其中称为起点，称为终点。显然此时弧与弧是不同的两条有向边。有向图的弧的起点称为弧头，弧的终点称为弧尾。有向图一般记为，其中为顶点集，为弧集。
例如图9.1 (C)可以表示为，顶点集，弧集为。
对于图除非指明是有向图，一般地，所谓的图都是指无向图。有向图也可以用表示。
例9.1 设，，其中
，，，，.
则是一个图，其图形如图9.2所示。

图9.2 非简单图示例
2.简单图和完全图
定义9.1 设是图的一条边，则称是的端点，并称与相邻，边与顶点（或）相关联。若两条边与有共同的端点，则称边与相邻；称有相同端点的两条边为重边；称两端点均相同的边为环；称不与任何边相关联的顶点为孤立点。
图9.2中，边与为重边，为环，顶点为孤立点。
定义9.2 无环且无重边的图称为简单图。
图9.2不是简单图，因为图中既含重边（与）又含环（）。
定义9.3 任意两点均相邻的简单图称为完全图。含个顶点的完全图记为。
3.赋权图
定义9.4 如果图的每条边都附有一个实数，则称图为赋权图，实数称为边的权。
赋权图也称为网络，如图9.1 (a)就是一个赋权图。赋权图中的权可以是距离、费用、时间、效益、成本等。
如果有向图的每条弧都被赋予了权，则称为有向赋权图。
4.顶点的度
定义9.5 （1）在无向图中，与顶点关联的边的数目（环算两次）称为的度，记为。
（2）在有向图中，从顶点引出的弧的数目称为的出度，记为，从顶点引入的弧的数目称为的入度，记为，称为的度。
度为奇数的顶点称为奇顶点，度为偶数的顶点称为偶顶点。
定理9.1 给定图，所有顶点的度数之和是边数的2倍，即
.
推论9.1 任何图中奇顶点的总数必为偶数。
5.子图
定义9.6 设与是两个图，并且满足，，则称是的子图。如是的子图，且，则称是的生成子图。
6.道路与回路
设，其中，，与和关联，称是图的一条道路，简称路，为路长，为起点，为终点；各边相异的道路称为迹（trail）；各顶点相异的道路称为轨道（path），记为；起点和终点重合的道路称为回路；起点和终点重合的轨道称为圈，即对轨道，当时成为一个圈。称以两顶点分别为起点和终点的最短轨道之长为顶点的距离。
7.连通图与非连通图
在无向图中，如果从顶点到顶点存在道路，则称顶点和是连通的。如果图中的任意两个顶点和都是连通的，则称图是连通图，否则称为非连通图。非连通图中的连通子图，称为连通分支。
在有向图中，如果对于任意两个顶点和，从到和从到都存在道路，则称图是强连通图。
9.1.2 图的矩阵表示
本节均假设图为简单图，其中，。
1.关联矩阵
对于无向图，其关联矩阵，其中

对有向图，其关联矩阵，其中

2.邻接矩阵
对无向非赋权图，其邻接矩阵，其中

对有向非赋权图，其邻接矩阵，其中

对无向赋权图，其邻接矩阵，其中

注9.1 当两个顶点之间不存在边时，根据实际问题的含义或算法需要，对应的权可以取为0或。
有向赋权图的邻接矩阵可类似定义。
例9.2 图9.3所示的无向图，其邻接矩阵为
.

图9.3 赋权无向图
用MATLAB重新画图9.3的程序如下：
clc, clear
a=zeros(5); %邻接矩阵初始化
a(1,[2:5])=[9 2 4 7]; a(2,[3 4])=[3 4]; %输入邻接矩阵的上三角元素
a(3,[4 5])=[8 4]; a(4,5)=6;
b=a+a'; %构造完整的邻接矩阵
s=cellstr(strcat('v',int2str([1:5]'))); %构造顶点字符串的细胞数组
c=graph(b,s); %构造无向图
plot(c,'EdgeLabel',c.Edges.Weight,'LineWidth',1.5); %画无向图
例9.3 图9.4所示的有向图的邻接矩阵为
.

图9.4 非赋权有向图
用MATLAB重新画图9.4的程序如下：
clc, clear
a=zeros(6); %邻接矩阵初始化
a(1,[2 3])=1; a(2,3)=1; a(3,[2 5])=1;
a(4,[2 6])=1; a(5,[2 4 6])=1; a(6,5)=1;
b=digraph(a) %生成有向图
plot(b) %画有向图
9.2 最短路算法及其MATLAB实现
最短路径问题是图论中非常经典的问题之一，旨在寻找图中两顶点之间的最短路径。作为一个基本工具，实际应用中的许多优化问题，如管道铺设、线路安排、厂区布局、设备更新等，都可被归结为最短路径问题来解决。
定义9.7 设图是赋权图，为中的一条路。则称的各边权之和为路的长度。
对于的两个顶点和，从到的路一般不止一条，其中最短的（长度最小的）一条称为从到的最短路；最短路的长称为从到的距离，记为。
求最短路的算法有Dijkstra（迪克斯特拉）标号算法和Floyd（弗洛伊德）算法等方法，但Dijkstra标号算法只适用于边权是非负的情形。最短路问题也可以归结为一个整数规划模型。
9.2.1 固定起点到其余各点的最短路算法
寻求从一固定起点到其余各点的最短路，最有效的算法之一是E. W. Dijkstra于1959年提出的Dijkstra算法。这个算法是一种迭代算法，它的依据是一个重要而明显的性质：最短路是一条路，最短路上的任一子段也是最短路。
对于给定的赋权图，其中为顶点集合，为边的集合，邻接矩阵，这里
（），
，.
为中的某个固定起点，求顶点到中另一顶点的最短距离。
Dijkstra算法的基本思想是：按距固定起点从近到远为顺序，依次求得到图各顶点的最短路和距离，直至某个顶点（或直至图的所有顶点）。
为避免重复并保留每一步的计算信息，对于任意顶点，定义两个标号：
：顶点的标号，表示从起点到的当前路的长度；
：顶点的父节点标号，用以确定最短路的路线。
另外用表示具有永久标号的顶点集。Dijkstra标号算法的计算步骤如下：
（1）令，对，令，，，。
（2）对每个（），令
，
这里表示顶点和之间边的权值，如果此次迭代利用顶点修改了顶点的标号值，则，否则不变。计算，把达到这个最小值的一个顶点记为，令。
（3）若或进入，算法终止；否则，用代替，转（2）。
算法结束时，从到各顶点的距离由的最后一次标号给出。在进入之前的标号叫T标号，进入时的标号叫P标号。算法就是不断修改各顶点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，至各顶点的最短路也在图上标示出来了。
例9.4 求图9.5所示的图中从到的最短路及最短距离。

图9.5 求最短距离的图
解 先写出邻接矩阵
.
Dijkstra算法计算过程的标号值如表9.1所示。
表9.1 Dijkstra算法计算过程的标号值
迭代次数
0
1
2
3
4
最终值

0

0

8
8
7
7
7

4
3

3

7
5

5

7
7
7
7
（或）

2

2

从表9.1可以看出，从到的最短路径长度为7。利用反向追踪可以得到最短路劲，的前驱节点（父节点）为或，的前驱节点为；的前驱节点为，的前驱节点为；所以可以得到两条最短路径，分别为
，.
MATLAB工具箱求两个指定的（单一）顶点最短路函数为shortestpath，其调用格式为
[path,d]=shortestpath(G,s,t,'Method',algorithm)
返回值path是求得的最短路径，d是求得的最短距离。
输入参数G是图的邻接矩阵，s是起点，t是终点，algorithm是一个字符串，指明属性'Method'的值，即所用的求最短路算法，algorithm可以取五种值：
（1）'auto' (缺省值)：自动选择'unweighted'、'positive'、'mixed'三种算法之一。
（2）'unweighted'：非赋权图，使用宽度优先搜索算法。
（3）'positive'：权值非负的赋权图，使用Dijkstra算法。
（4）'mixed'：在有向图中没有权值为负的圈，使用Bellman-Ford算法。
（5）'acyclic'：针对无圈有向赋权图。
求解上面最短路问题的MATLAB程序如下：
clc, clear, a=zeros(6);
a(1,[2,3,6])=[8,4,2]; a(2,3)=4; a(3,[4,6])=[2,1];
a(4,[5,6])=[2,5]; a(5,6)=5; %输入邻接矩阵的上三角元素
b=a+a'; c=graph(b) %构造赋权无向图
[p,d]=shortestpath(c,1,5) %求顶点1到5的最短路径和最短距离
9.2.2 每对顶点间的最短路算法
利用Dijkstra算法，当然还可以寻求赋权图中所有顶点对之间最短路。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行（为顶点个数）次这样的操作，就可得到每对顶点之间的最短路。但这样做需要大量的重复计算，效率不高。为此，R. W. Floyd另辟蹊径，于1962年提出了一个直接寻求任意两顶点之间最短路的算法。
对于赋权图，其中顶点集，邻接矩阵
，
这里
（），
，.
对于无向图，是对称矩阵，，。
Floyd算法是一个经典的动态规划算法，其基本思想是递推产生一个矩阵序列，其中矩阵，其第行第列元素表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。
计算时用迭代公式
，
是迭代次数，。
最后，当时，即是各顶点之间的最短通路值。
如果在求得两点间的最短距离时，还需要求得两点间的最短路径，需要在上面距离矩阵的迭代过程中，引入一个路由矩阵来记录两点间路径的前驱后继关系，其中表示从顶点到顶点的路径经过编号为的顶点。
路径矩阵的迭代过程如下：
（1）初始时
.
（2）迭代公式为
，
其中

直到迭代到，算法终止。
查找到最短路径的方法如下：
若，则点是顶点到顶点的最短路的中间点，然后用同样的方法再分头查找。若
（1）向顶点反向追踪得：，，，；
（2）向顶点正向追踪得：，，，；
则由点到的最短路径为：。
MATLAB工具箱求所有顶点对之间最短距离的命令为distances，其调用格式为
d=distances(G) %该命令只有一个返回值d，给出了所有顶点对之间的最短距离矩阵，而没有给出顶点对之间的最短路径。
例9.5 设为图9.6所示有向赋权图，求中任意两顶点之间的最短距离。

图9.6 有向赋权图
利用如下的MATLAB程序：
clc, clear, a=zeros(5);
a(1,2)=50; a(2,5)=80; a(3,[2,4])=[30,20];
a(4,5)=70; a(5,[1,3])=[60,100];
b=digraph(a) %构造赋权有向图
d=distances(b) %求所有顶点对之间的最短距离
求得所有顶点对之间的最短距离矩阵
，
从矩阵的第一行可以看出，的最短距离为50，的最短距离为230，的最短距离为250，的最短距离为130。
对于例9.5，如果要求所有顶点对之间的最短距离和最短路径，我们可以使用Dijkstra算法，调用10次shortestpath命令即可。如果使用Floyd算法，我们必须自己编程。
我们编写的求例9.5的最短距离和最短路径的MATLAB程序如下：
clc, clear, a=zeros(5);
a(1,2)=50; a(2,5)=80; a(3,[2,4])=[30,20];
a(4,5)=70; a(5,[1,3])=[60,100];
b=a; b(b==0)=inf; %构造数学上的邻接矩阵b
n=size(a,1); %顶点的个数
b(1:n+1:end)=0 %对角线元素赋0
r=zeros(n); %路由矩阵初始化
for k=1:n
for i=1:n
for j=1:n
if b(i,j)>b(i,k)+b(k,j)
b(i,j)=b(i,k)+b(k,j);
r(i,j)=k;
end
end
end
end
b, r %显示最短距离矩阵和路由矩阵
求得的最短距离矩阵与上面程序是一样的，求得的路由矩阵
.
由路由矩阵可知，到的最短路径为。这是因为（最短路径上，的前驱顶点为，的后继顶点为）；
（1）反向追踪：，（的直接前驱顶点为，不经过中间顶点）；
（2）正向追踪：，（的直接后继顶点为，不经过中间顶点）；
可知的后继为，的后继为，的后继为，的后继为，因而得出所求的最短路径。
9.2.3 最短路应用范例
例9.6（设备更新问题） 某种工程设备的役龄为4年，每年年初都面临着是否更新的问题：若卖旧买新，就要支付一定的购置费用；若继续使用，则要支付更多的维护费用，且使用年限越长维护费用越多。若役龄期内每年的年初购置价格、当年维护费用及年末剩余净值如表9.2所示。请为该设备制定一个4年役龄期内的更新计划，使总的支付费用最少。
表9.2 相关费用数据
年份
1
2
3
4
年初购置价格（万元）
25
26
28
31
当年维护费用（万元）
10
14
18
26
年末剩余净值（万元）
20
16
13
11
解 可以把这个问题化为图论中的最短路问题。
构造赋权有向图，其中顶点集，这里（）表示第年年初的时刻，表示第4年年末的时刻，为弧的集合，邻接矩阵，这里为第年年初至第年年初（或年年末）期间所支付的费用，计算公式为
，
其中为第年年初的购置价格，为使用到第年当年的维护费用，为第年年末旧设备的出售价格（残值）。则邻接矩阵
.
则制定总的支付费用最小的设备更新计划，就是在有向图中求从到的费用最短路。
利用Dijkstra算法，使用MATLAB软件，求得到的最短路径为，最短路径的长度为67。设备更新最小费用路径见图9.7中的粗线所示，即设备更新计划为第1年年初买进新设备，使用到第1年年底，第2年年初购进新设备，使用到第2年年底，第3年年初再购进新设备，使用到第4年年底。

图9.7 设备更新最小费用示意图
计算及画图的MATLAB程序如下：
clc, clear
p=[25,26,28,31]; a=[10,14,18,26]; r=[20,16,13,11];
b=zeros(5); %邻接矩阵（非数学上的邻接矩阵）初始化
for i=1:4
for j=i+1:5
b(i,j)=p(i)+sum(a(1:j-i))-r(j-i);
end
end
b, s=cellstr(strcat('v',int2str([1:5]'))); %构造顶点字符串的细胞数组
c=digraph(b,s); %构造赋权有向图
[p,d]=shortestpath(c,1,5)
h=plot(c,'Edgelabel',c.Edges.Weight,'Layout','force','EdgeColor','k')
highlight(h,p,'EdgeColor','r','LineWidth',2)
选址问题的类型很多，其中一类是为一个或几个服务设施在一定区域内选定它的位置，使某一指标达到最优值，具有代表性的是中心问题和重心问题。
中心问题 有些公共服务设施（例如仓库、急救中心、消防站等）的选址，要求网络中最远的被服务点距离服务设施的距离尽可能小。
例9.7 某连锁企业在某地区有6个销售点，已知该地区的交通网络如图9.8所示，其中点代表销售点，边表示公路，边上的数字表示销售点间公路距离，问仓库应建在哪个销售点，可使离仓库最远的销售点到仓库的路程最近？

图9.8 销售点间公路示意图
解 这是个选址问题，可以化为一系列求最短路问题。先求出到所有点的最短距离，令，表示若仓库建在，则离仓库最远的销售点距离为。再依次计算到所有点的最短距离，类似求出。（）中最小者即为所求，计算结果见表9.3。
表9.3 所有销售点间的两两距离
销售点

0
20
33
63
15
30
63

20
0
20
50
25
40
50

33
20
0
30
18
33
33

63
50
30
0
48
63
63

15
25
18
48
0
15
48

30
40
33
63
15
0
63
由于最小，所以仓库应建在，此时离仓库最远的销售点（和）距离为33。
计算的MATLAB程序如下
clc, clear, a=zeros(6);
a(1,[2 5])=[20 15]; a(2,[3:5])=[20 60 25];
a(3,[4 5])=[30 18]; a(5,6)=15; %输入邻接矩阵的上三角元素
[i,j,v]=find(a); %找矩阵a中非零元素的行地址、列地址及非零元素的取值
b=graph(i,j,v) %MATLAB另一种构造无向赋权图的方法
d=distances(b) %求所有顶点对之间的最短距离
d1=max(d,[],2) %逐行求最大值
[d2,ind]=min(d1) %求向量的最小值及最小值的地址
ind2=find(d(ind,:)==d2) %找ind行中哪个元素达到最大值
重心问题 有些公共服务设施（例如邮局、学校等）的选址，要求设施到所有服务对象点的距离总和最小。一般要考虑人口密度问题，或者全体被服务对象来往的总路程最短。
例9.8 某矿区有七个产矿点，如图9.9所示。已知各产矿点每天的产矿量（标在图9.9的各顶点旁）为吨，现要从这七个产矿点选一个来建造选矿厂，问应选在哪个产矿点，才能使各产矿点所产的矿石运到选矿厂所在地的总运力（吨·公里）最小。

图9.9 各产矿点分布图
解 令表示顶点与之间的距离。若选矿厂设在并且各产矿点到选矿厂的总运力为，则确定选矿厂的位置就转化为求，使得。
由于各产矿点到选矿厂的总运力依赖于任意两顶点之间的距离，即任意两顶点之间最短路的长度，因此可首先利用Floyd算法求出所有顶点对之间的最短距离，然后计算出顶点设立选矿厂时各产矿点到的总运力
.
具体的计算结果见表9.4。
表9.4 各顶点对之间的最短距离和总运力计算数据
产矿点

总运力

0
20
25
55
15
30
4850

20
0
20
40
25
40
4900

25
20
0
30
10
25
5250

55
40
30
0
40
55
11850

15
25
10
40
0
15
4700

30
40
25
55
15
0
8750
最后利用，求得为设置选矿厂的位置。
计算的MATLAB程序如下：
clc, clear, a=zeros(6);
a(1,[2 5])=[20 15]; a(2,[3:5])=[20 40 25];
a(3,[4 5])=[30 10]; a(5,6)=15; %输入邻接矩阵的上三角元素
b=graph(a+a'); %构造赋权无向图
d=distances(b) %求所有顶点对之间的最短距离
q=[80,90,30,20,60,10]'; m=d*q %计算总运力
[mm,ind]=min(m) %求最小运力
9.3 最小生成树算法及其MATLAB实现
树（tree）是图论中非常重要的一类图，它非常类似于自然界中的树，结构简单、应用广泛，最小生成树问题则是其中的经典问题之一。在实际应用中，许多问题的图论模型都是最小生成树，如通信网络建设、集成电话设计、有线电缆铺设、加工设备分组等。
9.3.1 基本概念
定义9.8 连通的无圈图称为树。
例如，图9.10给出的是树，但和则不是树。

图9.10 树与非树
定理9.2 设是具有个顶点条边的图，则以下命题等价。
（1）图是树；
（2）图中任意两个不同顶点之间存在唯一的路。
（3）图连通，删除任一条边均不连通；
（4）图连通，且；
（5）图无圈，添加任一条边可得唯一的圈；
（6）图无圈，且。
定义9.9 若图的生成子图是树，则称为的生成树或支撑树。
一个图的生成树通常不唯一。
定理9.3 连通图的生成树一定存在。
证明 给定连通图，若无圈，则本身就是自己的生成树。若有圈，则任取中一个圈，记删除中一条边后所得之图为。显然中圈已经不存在，但仍然连通。若中还有圈，再重复以上过程，直至得到一个无圈的连通图。易知是的生成树。
定理9.3的证明方法也是求生成树的一种方法，称为“破圈法”。
定义9.10 在赋权图中，边权之和最小的生成树称为的最小生成树。
一个简单连通图只要不是树，其生成树就不唯一，而且非常多。一般地，个顶点的完全图，其不同生成树的个数为。因而，寻求一个给定赋权图的最小生成树，一般是不能用枚举法的。例如，20个顶点的完全图有个生成树，有24位。所以，通过枚举求最小生成树是无效的算法，必须寻求有效的算法。
9.3.2 求最小生成树的算法
对于赋权连通图，其中为顶点集合，为边的集合，为邻接矩阵，这里顶点集合中有个顶点，构造它的最小生成树。构造连通图最小生成树的算法有Kruskal算法和Prim算法。
1.Kruskal算法
Kruskal算法思想：每次将一条权最小的边加入子图中，并保证不形成圈。
Kruskal算法如下：
（1）选，使得是权值最小的边。
（2）若已选好，则从中选取，使得
①中无圈，且
②是中权值最小的边。
（3）直到选得为止。
例9.9 用Kruskal算法求如图9.11所示连通图的最小生成树。

图9.11 构造最小生成树的连通图
解 首先将给定图的边按照权值从小到大进行排序，如表9.5所列。
表9.5 按照权值排列的边数据
边

取值
1
2
2
4
4
5
8
其次，依照Kruskal算法的步骤，迭代4步完成最小生成树的构造。按照边的排列顺序，前三次取定
，，；
由于下一个未选边中的最小权边与已选边构成圈，所以排除，第4次选，得到图9.12就是图的一颗最小生成树，它的权值是9。

图9.12 生成的最小生成树
2.Prim算法
设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为（空集）。Prim算法的思想是，从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。
Prim算法如下：
（1），；
（2）while
找最小边，其中；
；
；
end
例9.10（续例9.9） 用Prim算法求如图9.11所示连通图的最小生成树。
解 按照Prim算法的步骤，迭代4步完成最小生成树的构造。
（0）第0步初始化，顶点集，边集；
（1）第1步，找到最小边，，；
（2）第2步，找到最小边，，；
（3）第3步，找到最小边，，；
（4）第4步，找到最小边，，；最小生成树构造完毕。
9.3.3 用MATLAB求最小生成树及应用
1.MATLAB求最小生成树命令minspantree
MATLAB工具箱提供了一个求最小生成树的函数minspantree，利用这个函数可以实现求最小生成树的Prim算法和Kruskal算法。其调用格式为：
T=minspantree(G, 'Method',Value)
其中G为输入的图，Value的取值有两种：
（1）'dense'：为缺省值，使用Prim算法。
（2）'sparse'：使用Kruskal算法。
返回值T为所求得的最小生成树。
例9.11（续例9.9） 利用MATLAB的Kruskal算法求例9.9的最小生成树。
利用MATLAB求出的最小生成树的权值为9，所求的最小树如图9.13的粗线所示。

图9.13 MATLAB所画出的最小生成树
计算及画图的MATLAB程序如下：
clc, clear, a=zeros(5);
a(1,[2,3,5])=[8,4,2]; a(2,3)=4; %输入邻接矩阵上三角元素
a(3,[4,5])=[2,1]; a(4,5)=5;
s=cellstr(strcat('v',int2str([1:5]'))); %构造顶点字符串的细胞数据
b=graph(a+a',s); %构造无向赋权图
c=minspantree(b,'Method','sparse') %求最小生成树
L=sum(c.Edges.Weight) %求最小生成树的权值
h=plot(b,'Edgelabel',b.Edges.Weight,'Layout','subspace');
highlight(h,c) %加粗显示所生成的最小生成树
2.分组技术
分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少。最理想的情况是使每个零件的加工都在组内完成。
例9.12 现有13种零件，需在9台机器上加工。在各台机器上加工的零件号如表9.6所列。请将这9台机器分为3组，使零件跨组加工的情形尽量少。
表9.6 各台机器上加工的零件号
机器
1
2
3
4
5
6
7
8
9
加工的零件号
2,3,7,8,9,12,13
2,7,8,11,12
1,6
3,5,10
3,7,8,9,12,13
5
4,10
4,10
6
解 构造赋权图，其中，这里表示机器；为边的集合；为邻接矩阵，其元素
，
这里表示需由机器加工的零件集合，“”表示对称差，，表示集合中元素的个数，表示机器和的相异度。
显然，表达了两台不同机器加工零件的相异程度。分子为在机器但不在机器上加工，或在机器但不在机器上加工的零件数；分母为在机器或在机器上加工的零件数。特别地，表示机器与机器加工的零件完全相同；表示机器与机器加工的零件完全不相同。
图的最小生成树是由那些相异度最小的边构成的连通图，或看成是去掉了相异度相对比较大的边后余下的连通图。如果希望把机器分成个组，就继续删去最小生成树上权值最大的条边。于是得到个分离的子树，每棵树的顶点就构成了各机器组。
利用表9.6给出的数据，求得邻接矩阵
，
利用Prim算法求得的最小树如图9.14所示。将最小生成树中权值最大的两条边和去掉，得到三颗分离树，它们的顶点集分别为，，。因此，将9台机器按照标号
，，
分为3组时，可使零件跨组加工的情形尽量少。

图9.14 分组问题的最小生成树
计算及画图的MATLAB程序如下：
clc, clear, close all
[a,b]=xlsread('gdata9_12_1.xlsx');
a(isnan(a))=[] %删除a中的不确定值NaN
k=1;
for i=1:length(b)
if length(b{i})==0;
b{i}=a(k); k=k+1;
end
end
b{end+1}=a(k); %以上把数值数据和字符串数据合并
for i=1:length(b)
if ischar(b{i})
t1=b{i}; t2=['t=[',t1,']'];
eval(t2); %执行字符串对应的命令
c{i}=t; %把字符串数据改为数值型数据
else
c{i}=b{i};
end
end
celldisp(c) %显示细胞数组的所有元素
w=zeros(9); %邻接矩阵初始化
for i=1:8
for j=i+1:9
s1=unique(union(c{i},c{j})); %计算两个集合的并
s2=intersect(c{i},c{j}); %计算两个集合的交
s3=setdiff(s1,s2); %计算集合的差
w(i,j)=length(s3)/length(s1); %计算邻接矩阵的上三角元素
end
end
w1=w+w'; %得到数学上完整的邻接矩阵
xlswrite('gdata9_12_2.xlsx',w1) %为了做表，输出到Excel文件中
w2=w; w2(7,8)=0.0001; w2=graph(w2+w2'); %把0权值改为0.0001，并构造无向赋权图
T=minspantree(w2) %求最小生成树
T.Edges.Weight(end)=0; %恢复到原来的权重
plot(T,'Edgelabel',T.Edges.Weight,'Layout','circle') %画所求的最小生成树
注9.2 程序中celldisp(c)之前的语句为了生成数值型的细胞数组，等价于下列语句：
c={[2,3,7,8,9,12,13],[2,7,8,11,12],[1,6],[3,5,10],[3,7,8,9,12,13],5,[4,10],[4,10],6};
习题9
9.1 求图9.15的关联矩阵和邻接矩阵。

图9.15 非赋权无向图
9.2 求图9.16中从到的最短距离和最短路径。

图9.16 赋权无向图
9.3 求图9.16的最小生成树。
9.4 已知有6个村子，相互间道路的距离如图9.17所示。拟合建一所小学，已知处有小学生50人，处40人，处60人，处20人，处70人，处90人。问小学应建在哪一个村庄，使学生上学最方便（走的总路程最短）。

图9.17 村庄之间道路示意图
9.5 已知95个目标点的数据见Excel文件gex9_5.xlsx，第1列是这95个点的编号，第2,3列是这95个点的坐标，第4列是这些点重要性分类，标明“1”的是第一类重要目标点，标明“2”的是第二类重要目标点，未标明类别的是一般目标点，第5，6，7列标明了这些点的连接关系。如第三行的数据
C
-1160
587.5

D
F
表示顶点C的坐标为，它是一般目标点，C点和D点相连，C点也和F点相连。
完成如下问题：
（1）画出上面的无向图，一类重要目标点用“五角星”画出，二类重要点用“*”画出，一般目标点用“.”画出。这里要求画出无向图的度量图，即顶点的位置坐标必须准确，不要画出无向图的拓扑图。
（2）当边的权值为两点间的距离时，求上面无向图的最小生成树，并画出最小生成树。
（3）求顶点L到顶点M3的最短距离及最短路径，并画出最短路径。

251