图4无向图的最短路问避 编写LNGO程序如下： cities):w,x endsets w(1,2)=2:w(1,3)=8;w(1,4)=1: 3:4)-7:w3,5)=5:w(3,61=1:w(3,71=2: w(8,9)-7:w(8,11)=9; ft1ooads 8E88adsi,》:w(i,=eiw,"eq0,100,w4,; !城市的个数 .o. min-esum(roa 0:!不能同到项点1 endr (roads:@bin(x)) 与有向图相比较， 在程序中只增加了一个语句es(et1es):x5,1)=0,即 求得的最短路径为1 3.3每对顶点之间的最短路径 计算赋权图中各对项点之间最短路径，显然可以调用Dksr算法。具体方法是 每次以不同的顶点 点用DkS 的时间复杂度为O(n)。第二种解决这一问题的方法是由Floyd R W提出的算法，称 之为Floyd算法。 -78
-78- 图 4 无向图的最短路问题 编写 LINGO 程序如下： model: sets: cities/1.11/; roads(cities,cities):w,x; endsets data: w=0; enddata calc: w(1,2)=2;w(1,3)=8;w(1,4)=1; w(2,3)=6;w(2,5)=1; w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2; w(4,7)=9; w(5,6)=3;w(5,8)=2;w(5,9)=9; w(6,7)=4;w(6,9)=6; w(7,9)=3;w(7,10)=1; w(8,9)=7;w(8,11)=9; w(9,10)=1;w(9,11)=2;w(10,11)=4; @for(roads(i,j):w(i,j)=w(i,j)+w(j,i)); @for(roads(i,j):w(i,j)=@if(w(i,j) #eq# 0, 1000,w(i,j))); endcalc n=@size(cities); !城市的个数; min=@sum(roads:w*x); @for(cities(i)|i #ne#1 #and# i #ne# n:@sum(cities(j):x(i,j))=@sum(cities(j):x(j,i))); @sum(cities(j):x(1,j))=1; @sum(cities(j):x(j,1))=0; !不能回到顶点1; @sum(cities(j):x(j,n))=1; @for(roads:@bin(x)); end 与有向图相比较，在程序中只增加了一个语句@sum(cities(j):x(j,1))=0，即 从顶点 1 离开后，再不能回到该顶点。 求得的最短路径为 1→2→5→6→3→7→10→9→11，最短路径长度为 13。 3.3 每对顶点之间的最短路径 计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。具体方法是： 每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反 复执行 n −1次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法 的时间复杂度为 ( ) 3 O n 。第二种解决这一问题的方法是由 Floyd R W 提出的算法，称 之为 Floyd 算法
假设图G权的邻接矩阵为A, a11a12.a1w :. a2.a 来存放各边长度，其中 a=0 i=1.2.,n: 1,了之间没有边，在程序中以各边都不可能达到的充分大的数代替 ag=wgwg是i,j之间边的长度，1，j=1,2,.,n。 对于无向图，A是对称矩阵，a。=an· Floyd算法的基本思想是：递推产生一个矩阵序列A,A,A,An,其中 A,(,)表示从顶点”，到顶点"，的路径上所经过的顶点序号不大于k的最短路径长 度。 计算时用迭代公式： A亿，)=min(A-,)A-,k)+A-(k,j》 k是选代次数，i,k=1,2,.,n。 最后，当k=n时，An即是各顶点之间的最短通路值。 例12用F1ovd算法求解例g 矩阵Path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的 Matlab程序如下： clear;clc a=a+a':M-max(回ax(a)*n2;M为充分大的正实数 for j= if a,path 我们使用LINGO9.0编写的FLOYD算法如下 mode sets: -79
-79- 假设图G 权的邻接矩阵为 A0 ， ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = n n nn n n a a a a a a a a a A L M M L M L L 1 2 21 22 2 11 12 1 0 来存放各边长度，其中： aii = 0 i = 1,2,L,n ； aij = ∞ i, j 之间没有边，在程序中以各边都不可能达到的充分大的数代替； aij = wij wij 是i, j 之间边的长度，i, j = 1,2,L,n 。 对于无向图， A0 是对称矩阵，aij = a ji 。 Floyd 算法的基本思想是：递推产生一个矩阵序列 A A Ak An , , , , , 0 1 L L ，其中 A (i, j) k 表示从顶点 i v 到顶点 j v 的路径上所经过的顶点序号不大于 k 的最短路径长 度。 计算时用迭代公式： ( , ) min( ( , ), ( , ) ( , )) 1 1 1 A i j A i j A i k A k j k = k − k − + k − k 是迭代次数，i, j,k = 1,2,L,n 。 最后，当k = n 时， An 即是各顶点之间的最短通路值。 例12 用Floyd算法求解例9。 矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的 Matlab程序如下： clear;clc; n=6; a=zeros(n); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数 a=a+((a==0)-eye(n))*M; path=zeros(n); for k=1:n for i=1:n for j=1:n if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a, path 我们使用LINGO9.0编写的FLOYD算法如下： model: sets:
nodes/c1.c6/ ,nodes):w,pathpath标志最短路径上走过的顶项点， data: 00 P etext〔 (myd 十a1 te (enewline( writefor (nodes(j): calc: =50 =40 ：8}51,61=10 w(3,4）=10:w ,5 w5.61=55 for (link w(i,j)+w(j,1) 8roraoeg:eotae8{0F0fcd6gq0,10o0,w,): e。ana￥oi,5华#o ath(i,j));w(i,j)=tm))) §4树 4.1基本概念 连通的无圈图叫做树，记之为T。若图G满足V(G)=V(T),E(T)CE(G), 则称T是G的生成树。图G连通的充分必要条件为G有生成树。一个连通图的生成树 的个数很多，用x(G)表示G的生成树的个数，则有公式 公式(Caylay)r(Kn)=n-2。 公式t(G)=t(G-e)+r(G·e). 其中G-e表示从G上删除边e,G·e表示把e的长度收缩为零得到的图 树有下面常用的五个充要条件。 定理1()G是树当且仅当G中任二顶点之间有且仅有一条轨道。 (ii)G是树当且仅当G无圈，且￡=v-1。 (i)G是树当且仅当G连通，且￡=y-1 (iv)G是树当且仅当G连通，且e∈E(G),G-e不连通。 (v)G是树当且仅当G无圈，e任E(G),G+e恰有一个图。 42用一连线问题 欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为C,设计一个线 路图，使总造价最低 连线问题的数学模型是在连通赋权图上求权最小的生成树.赋权图的具最小权的生 成树叫做最小生成 的两 常用算法。 病不平殊袍中P用布故G的最小生成村中的项点，集合Q存放G
-80- nodes/c1.c6/; link(nodes,nodes):w,path; !path标志最短路径上走过的顶点; endsets data: path=0; w=0; @text(mydata1.txt)=@writefor(nodes(i):@writefor(nodes(j): @format(w(i,j),' 10.0f')),@newline(1)); @text(mydata1.txt)=@write(@newline(1)); @text(mydata1.txt)=@writefor(nodes(i):@writefor(nodes(j): @format(path(i,j),' 10.0f')),@newline(1)); enddata calc: w(1,2)=50;w(1,4)=40;w(1,5)=25;w(1,6)=10; w(2,3)=15;w(2,4)=20;w(2,6)=25; w(3,4)=10;w(3,5)=20; w(4,5)=10;w(4,6)=25;w(5,6)=55; @for(link(i,j):w(i,j)=w(i,j)+w(j,i)); @for(link(i,j) |i#ne#j:w(i,j)=@if(w(i,j)#eq#0,10000,w(i,j))); @for(nodes(k):@for(nodes(i):@for(nodes(j): tm=@smin(w(i,j),w(i,k)+w(k,j)); path(i,j)=@if(w(i,j)#gt# tm,k,path(i,j));w(i,j)=tm))); endcalc end §4 树 4.1 基本概念 连通的无圈图叫做树，记之为T 。若图G 满足V(G) =V(T ) ， E(T ) ⊂ E(G) ， 则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树 的个数很多，用τ (G) 表示G 的生成树的个数，则有公式 公式 (Caylay) 2 ( ) − = n τ Kn n 。 公式 τ (G) =τ (G − e) +τ (G ⋅ e) 。 其中G − e 表示从G 上删除边e ，G ⋅ e 表示把e 的长度收缩为零得到的图。 树有下面常用的五个充要条件。 定理 1 （i）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。 （ii）G 是树当且仅当G 无圈，且ε =ν −1。 （iii）G 是树当且仅当G 连通，且ε =ν −1。 （iv）G 是树当且仅当G 连通，且∀e∈ E(G) ，G − e 不连通。 （v）G 是树当且仅当G 无圈，∀e∉ E(G) ，G + e 恰有一个圈。 4.2 应用—连线问题 欲修筑连接 n 个城市的铁路，已知i 城与 j 城之间的铁路造价为Cij ，设计一个线 路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树。 下面介绍构造最小生成树的两种常用算法。 4.2.1 prim 算法构造最小生成树 设置两个集合 P 和Q ,其中 P 用于存放G 的最小生成树中的顶点，集合Q 存放G
的最小生成树中的边。今集合P的初值为P=”,}(假设构造最小生成树时，从顶点v 出发)，集合O的初值为O=Φ。Dim笔法的思根是，从所有D∈P,v∈V-P的边 中，选取具有最小权值的边m,将顶点v加入集合P中，将边p严加入集合Q中，如 此不断重复，直到P=V时，最小生成树构造完毕，这时集合Q中包含了最小生成树 的所有边。 prim算法如下： (i)P={y},Q=Φ： (ii)while P~=V 找最小边pm,其中p∈P,v∈V-P P=P+iv end 524 ②65 6" 图了最小生成树问题 例13用prm算法求图5的最小生成树。 我们用result的第 三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下 icicos (7): a (35 -50a 4,6=30:a4,71=42: a(5,6)=70 .en th(a) ttemp-tem 9a- min(ten ((( nd:p[p,)(ind(b) result 4.2.1 Kruskal算法构造最小生成树 科茹斯克尔(Kruskal)算法是一个好算法。Kruskal算法如下 (①选e,∈E(G),使得w(e)=min。 -81
-81- 的最小生成树中的边。令集合 P 的初值为 { }1 P = v （假设构造最小生成树时，从顶点 1 v 出发），集合Q 的初值为Q = Φ 。prim 算法的思想是，从所有 p ∈ P ，v ∈V − P 的边 中，选取具有最小权值的边 pv ，将顶点 v 加入集合 P 中，将边 pv 加入集合Q 中，如 此不断重复，直到 P =V 时，最小生成树构造完毕，这时集合Q 中包含了最小生成树 的所有边。 prim 算法如下： （i） { }1 P = v ，Q = Φ ； （ii）while P ~=V 找最小边 pv ，其中 p ∈ P,v ∈V − P P = P +{v} Q = Q +{pv} end 图 5 最小生成树问题 例 13 用 prim 算法求图 5 的最小生成树。 我们用 n result3× 的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下： clc;clear; a=zeros(7); a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; a=a+a';a(find(a==0))=inf; result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result 4.2.1 Kruskal 算法构造最小生成树 科茹斯克尔（Kruskal）算法是一个好算法。Kruskal 算法如下: (i)选 ( ) e1 ∈ E G ，使得 ( ) min w e1 =
(m若e,e2,.,e,已选好，则从E(G)-{e,e2,.,e,}中选取e,1,使得 ①G[{e,e2,.,e,e1}】中无圈，且 ②wv(e.,)=min. (i直到选得e-为止 例14用Kruskal算法构造例3的最小生成树。 我们用imdx,m存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u改记为此边的另一序号v,同时把后面边中所有序号为u的改记为v。 此方法的几何意义是：将序号4的这个顶点收缩到v顶点，4顶点不复存在。后面继续 寻查时，发现某边的两个项点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab程序如下： 8:e86:a,31=60:a2,4-65a2,51=40 ;index=data(1:2,:); 8ize(a)-1; flag-flag(1); ina (1 result=[result,data(:,flag)l; ndex (ind (indexv2))v1 result $5匹配向题 定义若McE(G),e,C,∈M,g与e,无公共端点(i≠j),则称M为图 G中的一个对集：M中的一条边的两个端点叫做在对集M中相配：M中的端点称为 被M许配：G中每个顶点皆被M许配时，M称为完美对集：G中已无使|MlM 的对集M,则M称为最大对集：若G中有一轨，其边交替地在对集M内外出现，则 称此轨为M的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。 若把可增广轨上在M外的边纳入对集，把M内的边从对集中删除，则被许配的 顶点数增加2，对集中的“对儿”增加一个。 1957年，贝尔热(Berge)得到最大对集的充要条件： 足理2 M是图G中的最大对集当且仅当G中无M可增广轨。 933 ，霍尔al)得到下面的许配 定理3G为二分图，X与Y是项点集的划分，G中存在把X中顶点皆许配的 -82
-82- (ii)若 i e ,e , ,e 1 2 L 已选好，则从 ( ) { , , , } 1 2 i E G − e e L e 中选取 i+1 e ，使得 ① [{ , , , , }] 1 2 i i+1 G e e L e e 中无圈，且 ② w(ei+1 ) = min 。 (iii)直到选得 ν −1 e 为止。 例 14 用 Kruskal 算法构造例 3 的最小生成树。 我们用 n index2× 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序 号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。 此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续 寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab 程序如下： clc;clear; a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30; a(4,7)=42; a(5,6)=70; [i,j,b]=find(a); data=[i';j';b'];index=data(1:2,:); loop=max(size(a))-1; result=[]; while length(result)<loop temp=min(data(3,:)); flag=find(data(3,:)==temp); flag=flag(1); v1=data(1,flag);v2=data(2,flag); if index(1,flag)~=index(2,flag) result=[result,data(:,flag)]; end index(find(index==v2))=v1; data(:,flag)=[]; index(:,flag)=[]; end result §5 匹配问题 定义 若 M ⊂ E(G) ，∀ei ,e j ∈ M ， i e 与 j e 无公共端点（i ≠ j ），则称 M 为图 G 中的一个对集；M 中的一条边的两个端点叫做在对集 M 中相配；M 中的端点称为 被 M 许配；G 中每个顶点皆被 M 许配时，M 称为完美对集；G 中已无使| M '|>| M | 的对集 M ' ，则 M 称为最大对集；若G 中有一轨，其边交替地在对集 M 内外出现，则 称此轨为 M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。 若把可增广轨上在 M 外的边纳入对集，把 M 内的边从对集中删除，则被许配的 顶点数增加 2，对集中的“对儿”增加一个。 1957 年，贝尔热(Berge)得到最大对集的充要条件： 定理 2 M 是图G 中的最大对集当且仅当G 中无 M 可增广轨。 1935 年，霍尔(Hall)得到下面的许配定理： 定理 3 G 为二分图， X 与Y 是顶点集的划分，G 中存在把 X 中顶点皆许配的