图4无向图的最短路问题 编写 LINGO程序如下 model cities/1.11/ roads(cities, cities):w,x endsets enddata (1,2)=2;w(1,3)=8;w(1,4)=1; W(2,3)=6;(2,5)=1; W(3,4)=7;(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;(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(,3): w(i,j)=w(i,3)+w(3, i)) efor(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)i @for(cities(i)li #ne#1 #and# i #ne# n: Gsum(cities (3):x(i,3))=@sum(cities(3): x(3, 1)))i @sum(cities(3): x(1,3))=1 esum( cities(j):x(,1))=0;!不能回到顶点1 @sum(cities(3):x(G, n))=l @for(roads: @bin(x))i end 与有向图相比较,在程序中只增加了一个语句sum( cities(j):x(方,1))=0,即 从顶点1离开后,再不能回到该顶点。 求得的最短路径为1→2→5→6-37→10→9→11,最短路径长度为13。 3.3每对顶点之间的最短路径 计算赋权图中各对顶点之间最短路径,显然可以调用 Dijkstra算法。具体方法是: 每次以不同的顶点作为起点,用 Dijkstra算法求出从该起点到其余顶点的最短路径,反 复执行n-1次这样的操作,就可得到从每一个顶点到其它顶点的最短路径。这种算法 的时间复杂度为O(n3)。第二种解决这一问题的方法是由 Floyd r w提出的算法,称 之为 Floyd算法
-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 a1 A o n2 来存放各边长度,其中 0i=1,2 an=∞i,j之间没有边,在程序中以各边都不可能达到的充分大的数代替 a=WWg是i,j之间边的长度,i,j=1,2…,n 对于无向图,4是对称矩阵,an=aB Floyd算法的基本思想是:递推产生一个矩阵序列A,A1,…A…An,其中 4(2j)表示从顶点v到顶点v的路径上所经过的顶点序号不大于k的最短路径长 计算时用迭代公式 A(,j=min(A-(i,)), Ak(,k)+A-(k,DD) k是迭代次数,i,jk=1,2…,n。 最后,当k=n时,A,即是各顶点之间的最短通路值 例12用 Floyd算法求解例9。 矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。 Floyd算法的 Matlab程序如下: clear: clc a=zeros 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;为充分大的正实数 +((a==0)-eye(n))*M; path=zeros(n) for k=l: n for i=l:n if a(i, j)>a(i, k) a (i,j)=a(i, k)+a(k,3)i path(i, j)=k a, path 我们使用 LINGO9.0编写的 FLOYD算法如下
-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/cl.c6/ 1ink( nodes, nodes):w,path;!path标志最短路径上走过的顶点 endsets data path=0 @text(mydatal. txt)=Gwritefor (nodes (1): writefor (nodes (j) @format(w(i,3),10.0f)), newline(1) @text(mydatal. txt)=Write(@newline(1)) etext (mydatal. txt)=Gwritefor(nodes(i): @writefor (nodes(3): @format (path(i,3), 10.0f )) Newline(1) enddata 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 for(1ink(i,j):w(i,j)=w(i,j)+w(,i)); @for (link(i,3) li#ne#j: w(i,j)=@if(w(i,3)#eq#0, 10000,w(1,3))) @for(nodes(k): Gfor(nodes (i): @for(nodes(j) tm=@smin(w(i,3),w(i, k)+w(k,3))i endc bath(i, j)=@if((i, j)#gt# tm, k, path(i, 3));w(i, j)=tm)))i §4树 4.1基本概念 连通的无圈图叫做树,记之为T。若图G满足V(G)=(T),E(T)cE(G), 则称T是G的生成树。图G连通的充分必要条件为G有生成树。一个连通图的生成树 的个数很多,用r(G)表示G的生成树的个数,则有公式 公式( Caylay,)r(Kn)=n"-2 公式r(G)=r(G-e)+r(G·e)。 其中G-已表示从G上删除边e,G·e表示把e的长度收缩为零得到的图。 树有下面常用的五个充要条件。 定理1(i)G是树当且仅当G中任二顶点之间有且仅有一条轨道 (i)G是树当且仅当G无圈,且E=V-1。 (i)G是树当且仅当G连通,且E=v-1。 (iv)G是树当且仅当G连通,且ve∈E(G),G-e不连通 (v)G是树当且仅当G无圈,ve∈E(G),G+e恰有一个圈 42应用一连线问题 欲修筑连接η个城市的铁路,已知i城与j城之间的铁路造价为C,设计一个线 路图,使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树 下面介绍构造最小生成树的两种常用算法。 421prim算法构造最小生成树 设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点,集合Q存放G 80
-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={v1}(假设构造最小生成树时,从顶点v 出发),集合Q的初值为Q=Φ。pim算法的思想是,从所有p∈P,v∈V-P的边 中,选取具有最小权值的边p,将顶点v加入集合P中,将边p加入集合Q中,如 此不断重复,直到P=V时,最小生成树构造完毕,这时集合Q中包含了最小生成树 的所有边。 prim算法如下 (i)P={v1},Q (ii while P=v 找最小边p,其中p∈P,∈-P P=P+v) Q=0+pv) 50 图5最小生成树问题 例13用prim算法求图5的最小生成树 我们用 result3xn的第一、二、三行分别表示生成树边的起点、终点、权集合。 Matlab 程序如下 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+ ia(find(a==0))=inf result=llip=l; tb=2: length(a) while length(result)x=length(a)-1 temp=a(p, tb)i temp=temp(: )i d=min(temp)i [jb, kb]=find (a(p, th)==d)i j=p(3b(1))ik=tb(kb(1) result=[result, [jikid]lip=lp, k] tb(find(tb==k))=[] 42.1 Kruskal算法构造最小生成树 科茹斯克尔( Kruskal)算法是一个好算法。 Kruskal算法如下: (选e1∈E(G),使得w(e1)=min
-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 =
(i)若e1,e2…,e1已选好,则从E(G)-{e1e2,…,e}中选取e+1,使得 ①G[{e,e2;…,e1,en}中无圈,且 (i)直到选得e为止。 例14用 Kruskal算法构造例3的最小生成树 我们用 index,存放各边端点的信息,当选中某一边之后,就将此边对应的顶点序 号中较大序号l改记为此边的另一序号v,同时把后面边中所有序号为u的改记为 此方法的几何意义是:将序号u的这个顶点收缩到ν顶点,l顶点不复存在。后面继续 寻查时,发现某边的两个顶点序号相同时,认为已被收缩掉,失去了被选取的资格。 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,3,b]=find(a)i data=[i b']; index=data(1: 2,:)i loop=max(size(a))-li result=[i le length(result)<loop temp=min(data(3,: ))i flag=find (data(3,: )==temp)i flag=flag(1) vl=data(l, flag)iv2=data(2, flag)i if index(1, flag)-=index(2, flag) result=[result, data(:, flag)] end index( find(index==v2))=vli data(:, flag)=[I index(:, flag)=[] end result §5匹配问题 定义若McE(G),Ve,e,∈M,e与e,无公共端点(i≠j),则称M为图 G中的一个对集;M中的一条边的两个端点叫做在对集M中相配;M中的端点称为 被M许配;G中每个顶点皆被M许配时,M称为完美对集;G中已无使|MpM 的对集M,则M称为最大对集;若G中有一轨,其边交替地在对集M内外出现,则 称此轨为M的交错轨,交错轨的起止顶点都未被许配时,此交错轨称为可增广轨。 若把可增广轨上在M外的边纳入对集,把M内的边从对集中删除,则被许配的 顶点数增加2,对集中的“对儿”增加一个 1957年,贝尔热 Berge)得到最大对集的充要条件 定理2M是图G中的最大对集当且仅当G中无M可增广轨。 1935年,霍尔(Ha)得到下面的许配定理 定理3G为二分图,X与Y是顶点集的划分,G中存在把X中顶点皆许配的
-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 中顶点皆许配的