行遍性问题 1.欧拉图 连通图G(V,E)中,若从某个顶点出发,经过有 限条边(这些边构成的子集记为E1)、有限个顶点(这 些点构成的子集记为V),又回到了出发点,且整个 行进过程中,每条边、每个顶点都没有被重复经过, 则称子图G(1,E)是一个回路(或称:一个圈) 性质:若图中边的个数不小于顶点个数,则必有 回路 连通图G(V,E)中,若从某个顶点出发,G的每条 边恰好经过一次,又可回到出发点,则称该路径为欧 拉路,称该图为欧拉图 定理1对于连通图G(V,E),下面三条相互等价 (1)G是一个欧拉图 (2)G的每个顶点的次数都是偶数 3)边集E可划分成多个子集(子集之间两两不 相交,全体子集之并等于E),使得每个子集都单独 构成一个回路 证明(1)→(2):存在欧拉路C,考虑任一顶点w C每次经过v时,总是既有来边、也有去边,与v关 联的每条边都要被C经过一次,所以与v关联的边数 (即:v的次数)必为偶数。 (2)→(3):每个顶点次数均为偶数,根据“顶点 次数之和等于二倍的边数”得,边数不小于顶点个数, G必有回路,设G(V,E1)是一个回路。考虑E\E1构 成的子图,其顶点均为偶次,故必有回路。依次类推, 因G是有限图,故可得有限个回路G2…,G,使得 G=G1UG2U…UG (3)→(1):已知G是由若干个回路合并而成。选 定一个顶点作为出发点,第一步(即第一条边)必在某 个回路上,该回路记为C1,沿C1前进,若某个顶点 处与另一回路相交,则记新回路为C2,并立即沿C2 走 不失一般性,设你正沿着C走,在某个 点处又与别的回路相交,先判断该回路是不是 C1C2…Ca1其中一,若是则不管,若不是则记新回 路为Ca1并沿着它走,按上述规则就可以走出一条 欧拉路.证毕
行遍性问题 1. 欧拉图 连通图 G(V,E)中，若从某个顶点出发，经过有 限条边（这些边构成的子集记为 E1 ）、有限个顶点（这 些点构成的子集记为 V1 ），又回到了出发点，且整个 行进过程中，每条边、每个顶点都没有被重复经过， 则称子图 ( , ) G1 V1 E1 是一个回路（或称：一个圈）. 性质：若图中边的个数不小于顶点个数，则必有 回路 连通图 G(V,E)中，若从某个顶点出发，G 的每条 边恰好经过一次，又可回到出发点，则称该路径为欧 拉路，称该图为欧拉图. 定理 1 对于连通图 G(V,E)，下面三条相互等价： (1) G 是一个欧拉图； (2) G 的每个顶点的次数都是偶数； (3) 边集 E 可划分成多个子集（子集之间两两不 相交，全体子集之并等于 E），使得每个子集都单独 构成一个回路. 证明 (1) (2) ：存在欧拉路 C，考虑任一顶点 v， C 每次经过 v 时，总是既有来边、也有去边，与 v 关 联的每条边都要被 C 经过一次，所以与 v 关联的边数 （即：v 的次数）必为偶数。 (2) (3) ：每个顶点次数均为偶数，根据“顶点 次数之和等于二倍的边数”得，边数不小于顶点个数， G 必有回路，设 ( , ) G1 V1 E1 是一个回路。考虑 1 E \ E 构 成的子图，其顶点均为偶次，故必有回路。依次类推， 因 G 是有限图，故可得有限个回路 G Gr , , 2 ，使得 G = G1 G2 Gr . (3) (1) ：已知 G 是由若干个回路合并而成。选 定一个顶点作为出发点，第一步(即第一条边)必在某 个回路上，该回路记为 C1 ，沿 C1 前进，若某个顶点 处与另一回路相交，则记新回路为 C2 ，并立即沿 C2 走， . 不失一般性，设你正沿着 Ci 走，在某个 点处又与别的回路相交，先判断该回路是不是 1 2 1 , , , C C Ci− 其中一，若是则不管，若不是则记新回 路为Ci+1 并沿着它走. 按上述规则就可以走出一条 欧拉路. 证毕
2.中国邮递员问题 问题:邮递员发送邮件,从邮局出发,辖区范围 内的每条街道经过至少一次,回到邮局。确定路线 使总路程最短。 建模:街道=边:街道长≡=权;街道交叉口== 顶点;邮局=顶点;辖区=赋权连通图G 下面分三种情况: (1)G的顶点都是偶次 此时,G是欧拉图,只需求出一个欧拉路即可, 用 Fleury算法: 定义:连通图的任一条边,若删除该边后使得图 不再连通,则称该边为一条割边。 Fleury思路:每当要走一条边之前,先判断, 在全体未被走过的边构成的子图中,该边是否为割 边,若是则不走。 (2)G只有两个顶点是奇次 先求那两个奇次顶点之间的最短路(用 Dijkstra 算法),该路记为P.将P加入G(相当于在G中又 适当增加了一些边),构成新的图,新图必为欧拉图 用(1)的方法求出一个欧拉路作为行进路线即可 (3)G的奇次顶点个数大于2 因任何一个图的奇次顶点个数必是偶数,故可将 奇次顶点两两配对。我们的目标是:适当配对,使得 每对顶点之间的最短路长之和达到最小。将这些路加 入G构成新欧拉图,用(1)的方法求出一个欧拉路 作为行进路线即可 例:求最佳邮递路线,G(V,E),V={n1"2…v} v12(4),vv7()2V2(2),v2V4(5),v2V(2),vyv4(1) E={vv3(1)v4v3(3),v2V(8)v3v6(10,vv2(D)v23(9), v719(6),v8v9(3) 解:4个顶点{v4,Vn,32}是奇次,先求他们之间 的最短路 P(v4,V7)=v4V2V7,d(v4,V7)=5 P(v4,18)=v48, d(v4, v8)=3 P(4, V9)=viVo, d(v4, v9)=6 P(v7, 18)=v,8, d(v,, vs) P(v7, v9) d(v7,v)=6 P(8, v9)=18 d (vs, v9)=3 再求这4个点之间的最佳配对,当4与7配对、8与 9配对时,距离之和达到最小5+3=8 在G中添加路径vv"2V与vv,形成一个欧拉 图,该图的任意一条欧拉路都是最佳邮递路线
2. 中国邮递员问题 问题：邮递员发送邮件，从邮局出发，辖区范围 内的每条街道经过至少一次，回到邮局。确定路线， 使总路程最短。 建模：街道==边；街道长==权；街道交叉口== 顶点；邮局==顶点；辖区==赋权连通图 G . 下面分三种情况： （1）G 的顶点都是偶次 此时，G 是欧拉图，只需求出一个欧拉路即可， 用 Fleury 算法： 定义：连通图的任一条边，若删除该边后使得图 不再连通，则称该边为一条割边。 Fleury 思路：每当要走一条边之前，先判断， 在全体未被走过的边构成的子图中，该边是否为割 边，若是则不走。 （2）G 只有两个顶点是奇次 先求那两个奇次顶点之间的最短路(用 Dijkstra 算法)，该路记为 P . 将 P 加入 G（相当于在 G 中又 适当增加了一些边），构成新的图，新图必为欧拉图， 用（1）的方法求出一个欧拉路作为行进路线即可。 （3）G 的奇次顶点个数大于 2 因任何一个图的奇次顶点个数必是偶数，故可将 奇次顶点两两配对。我们的目标是：适当配对，使得 每对顶点之间的最短路长之和达到最小。将这些路加 入 G 构成新欧拉图，用（1）的方法求出一个欧拉路 作为行进路线即可。 例：求最佳邮递路线，G(V,E),V={ 1 2 9 v ,v , ,v }, E={ (6), (3) (1), (3), (8), (10), (1), (9), (4), (1), (2), (5), (2), (1), 7 9 8 9 4 5 4 8 4 9 5 6 6 7 7 8 1 2 1 7 2 3 2 4 2 7 3 4 v v v v v v v v v v v v v v v v v v v v v v v v v v v v } 解：4 个顶点 { , , , } 4 7 8 9 v v v v 是奇次，先求他们之间 的最短路 ( , ) , ( , ) 3 ( , ) , ( , ) 6 ( , ) , ( , ) 9 ( , ) , ( , ) 6 ( , ) , ( , ) 3 ( , ) , ( , ) 5 8 9 8 9 8 9 7 9 7 9 7 9 7 8 7 8 7 8 4 9 4 8 9 4 9 4 8 4 8 4 8 4 7 4 3 2 7 4 7 = = = = = = = = = = = = P v v v v d v v P v v v v d v v P v v v v d v v P v v v v v d v v P v v v v d v v P v v v v v v d v v 再求这 4 个点之间的最佳配对，当 4 与 7 配对、8 与 9 配对时，距离之和达到最小 5+3=8. 在 G 中添加路径 4 3 2 7 v v v v 与 8 9 v v ，形成一个欧拉 图，该图的任意一条欧拉路都是最佳邮递路线
题:求最佳邮递路线 3 3 2 3.推销员问题 流动推销员需要访问某地区的所有城镇,最后回 到出发点.问如何安排旅行路线使总行程最小.这就 是推销员问题 最佳推销员回路问题解法:由给定的图G=(VE) 构造一个以V为顶点集的完备图G=(V,E),E的 每条边(xy)的权等于顶点x与y在图中最短路的权 例对一个完备图,用二边逐次修正法求最佳推 销员回路见文件“第9讲行遍性问题pt”) ear n=6: bbb=0 [0,56,35,2,51, 0,0,21,57,78,70 0,0,0,36,68,68; 0,0,0,0,51,6 0,0,0,0,0,13 0,0,0,0,0,0 for i=2: n for j=l: i-1 (i, j)=a(j, i) nd end (n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1 while bbb==0 rj=3:n for 1=1: j-2 if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1) bbb=0 for k=i+l: j b(k,:)=a(j+i+1-k,:) for 1=i+l: j b(:,1)=a(:,j+i+1-1)
题：求最佳邮递路线 3 2 3 4 3 4 1 2 2 3 3 3 1 3 2 3 3. 推销员问题 流动推销员需要访问某地区的所有城镇，最后回 到出发点．问如何安排旅行路线使总行程最小．这就 是推销员问题 最佳推销员回路问题解法：由给定的图 G=(V,E) 构造一个以 V 为顶点集的完备图 G’=(V,E’)，E’的 每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权． 例 对一个完备图，用二边逐次修正法求最佳推 销员回路 （见文件“第 9 讲 行遍性问题.ppt”） clear n=6;bbb=0; a=[0,56,35,2,51,60; 0,0,21,57,78,70; 0,0,0,36,68,68; 0,0,0,0,51,61; 0,0,0,0,0,13 0,0,0,0,0,0]; for i=2:n for j=1:i-1 a(i,j)=a(j,i); end end a(n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1; while bbb==0 bbb=1; for j=3:n for i=1:j-2 if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1) bbb=0; for k=i+1:j b(k,:)=a(j+i+1-k,:); end a=b; for l=i+1:j b(:,l)=a(:,j+i+1-l); end
a=b;a(n,n+1)=a(m,1);xb=[1:i,j:-1:i+1,j+1:n+1] kk=xb ii): cxl(ii)=cx(kk) Cx=CXI end d 执行结果: 5 6 251605 2051615736 5151 01378 60611307068 56577870 021 35366868210 8 u 6
a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1] ; for ii=1:n+1 kk=xb(ii);cx1(ii)=cx(kk); end cx=cx1; i=j-2;j=n; end end end end cx,a(1:n,1:n) 执行结果： cx = 1 4 5 6 2 3 7 ans = 0 2 51 60 56 35 2 0 51 61 57 36 51 51 0 13 78 68 60 61 13 0 70 68 56 57 78 70 0 21 35 36 68 68 21 0
例:求最佳推销员回路 02 8∞∞ 1∞07∞∞9∞ 解:邻接矩阵C 86705 o1∞503∞9 ∞92∞40 630 963 步1:在原来9个顶点的基础上构造一个完备图 每条边的权等于“与它关联的两顶点之间”在原图中 的最短路权 记Cl=C,做递推计算Ck=Ck-C,k=2,3,4, (这里的乘法是第i行与第j列之元素对应向加之最小值。) 程序清单: clear c=intones(8, 8) c(n)=0; end c(1,2)=2;c(1,3)=1;c(1,4)=8;c(24)=6c(2,5)=1;c(3,4)=7c (3,7)=9c(4,5)=5;c(46=1c(4,7)=2c(5,6)=3;c(5,8)9;c( 6,7)=4c(6,8)=6;c(78=3 for i =1: 7 or J- c, IFc(LD) d=c for xh=1: 10 for i=1 8 a(i,jAmin((i,: +c( a=d 执行结果 4710 036 6 7 0 3 97 9 5704125 6 3 0 12 6 3 这就是所求完备图的邻接矩阵
例：求最佳推销员回路. 解：邻接矩阵 = 9 6 3 0 9 2 4 0 3 1 3 0 4 6 1 5 0 3 9 8 6 7 0 5 1 2 1 0 7 9 2 0 6 1 0 2 1 8 C 步 1：在原来 9 个顶点的基础上构造一个完备图， 每条边的权等于“与它关联的两顶点之间”在原图中 的最短路权． 记 C1=C，做递推计算 Ck=Ck-1C，k=2,3,4,……， （这里的乘法是第 i 行与第 j 列之元素对应向加之最小值。） 程序清单： clear c=inf*ones(8,8); for i=1:8 c(i,i)=0; end c(1,2)=2;c(1,3)=1;c(1,4)=8;c(2,4)=6;c(2,5)=1;c(3,4)=7;c (3,7)=9;c(4,5)=5;c(4,6)=1;c(4,7)=2;c(5,6)=3;c(5,8)=9;c( 6,7)=4;c(6,8)=6;c(7,8)=3; for i=1:7 for j=i+1:8 c(j,i)=c(i,j); end end d=c, for xh=1:10 for i=1:8 for j=1:8 a(i,j)=min(d(i,:)+c(:,j)'); end end xhcs=xh+1;d=a; end a=d 执行结果： a = 0 2 1 7 3 6 9 12 2 0 3 5 1 4 7 10 1 3 0 7 4 7 9 12 7 5 7 0 4 1 2 5 3 1 4 4 0 3 6 9 6 4 7 1 3 0 3 6 9 7 9 2 6 3 0 3 12 10 12 5 9 6 3 0 这就是所求完备图的邻接矩阵
步2:针对完备图,用二边逐次修正法求出最佳 推销员回路 (续前一个程序) a(n,n+1)=a(n,1);b=a;cx=1:n+1;cxl=1:n+1; Thile bbb==o f a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1) b(k,:)=a(j+i+1-k,:) for I=i+l: j b(:,1)=a(:,j+i+1-1) a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1] for ii=l: n+I kk=xb(ii); cxl(ii)=cx(kk) end 1(1:n,1:n) 执行结果 138746529 即,最佳推销员路线是: 012 0 0 34964 2 6 7 6 0 3 3 6 3 0 310 即,路线长度是:1+12+3+2+1+3+1+2==25.完毕
步 2：针对完备图，用二边逐次修正法求出最佳 推销员回路。 （续前一个程序） n=8;bbb=0; a(n,n+1)=a(n,1);b=a;cx=1:n+1;cx1=1:n+1; while bbb==0 bbb=1; for j=3:n for i=1:j-2 if a(i,i+1)+a(j,j+1)>a(i,j)+a(i+1,j+1) bbb=0; for k=i+1:j b(k,:)=a(j+i+1-k,:); end a=b; for l=i+1:j b(:,l)=a(:,j+i+1-l); end a=b;a(n,n+1)=a(n,1);xb=[1:i,j:-1:i+1,j+1:n+1] ; for ii=1:n+1 kk=xb(ii);cx1(ii)=cx(kk); end cx=cx1; i=j-2;j=n; end end end end cx,a(1:n,1:n) 执行结果： cx = 1 3 8 7 4 6 5 2 9 即，最佳推销员路线是： u0---u2---u7---u6---u3---u5---u4---u1---u0. ans = 0 1 12 9 7 6 3 2 1 0 12 9 7 7 4 3 12 12 0 3 5 6 9 10 9 9 3 0 2 3 6 7 7 7 5 2 0 1 4 5 6 7 6 3 1 0 3 4 3 4 9 6 4 3 0 1 2 3 10 7 5 4 1 0 即，路线长度是：1+12+3+2+1+3+1+2 == 25. 完毕