资源描述：
《行遍性问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、行遍性问题1.欧拉图连通图G(V,E)中，若从某个顶点出发，经过有限条边(这些边构成的子集记为色)、有限个顶点(这些点构成的子集记为％),又回到了出发点，且整个行进过程中，每条边、每个顶点都没有被重复经过，则称子图)是一个回路(或称：一个圈).性质：若图中边的个数不小于顶点个数，则必有回路连通图G(V,E)中，若从某个顶点出发，G的每条边恰好经过一次，又可回到出发点，则称该路径为欧拉路，称该图为欧拉图.定理1对于连通图G(V,E),下面三条相互等价：(1)G是一个欧拉图；(2)G的每个顶点的次数都是偶数；(3)边集E可划分成多个子集(子集之间两两不相交，全体子集之并等于E),使得每个子集都单独
2、构成一个回路.证明存在欧拉路C,考虑任一顶点v,C每次经过v时，总是既有来边、也有去边，与v关联的每条边都要被C经过一次，所以与v关联的边数(即：v的次数)必为偶数。(2)=>(3);每个顶点次数均为偶数，根据“顶点次数之和等于二倍的边数”得，边数不小于顶点个数，G必有回路，设°1(%卫1)是一个回路。考虑E'E构成的子图，其顶点均为偶次，故必有回路。依次类推，因G是有限图，故可得有限个回路Q,使得G=G1G2G,(3)=(1)：已知G是由若干个回路合并而成。选定一个顶点作为出发点,第一步(即第一条边)必在某个回路上，该回路记为q,沿q前进，若某个顶点处与另一冋路相交，则记新冋路为G,并立即
3、沿°2走，.不失一般性，设你正沿着'走，在某个点处又与别的回路相交，先判断该回路是不是566其中一，若是则不管，若不是则记新回路为°沖】并沿着它走.按上述规则就可以走出一条欧拉路.证毕.2.中国邮递员问题问题：邮递员发送邮件，从邮局出发，辖区范围内的每条街道经过至少一次，回到邮局。确定路线，使总路程最短。建模：街道二二边；街道长二二权；街道交叉口二二顶点；邮局二二顶点；辖区二二赋权连通图G・下面分三种情况：（1）G的顶点都是偶次此时，G是欧拉图，只需求出一个欧拉路即可，用Fleury算法：定义：连通图的任一条边，若删除该边后使得图不再连通，则称该边为一条割边。Fleury思路：每当要走一条边之
4、前，先判断，在全体未被走过的边构成的子图中，该边是否为割边，若是则不走。（2）G只有两个顶点是奇次先求那两个奇次顶点之间的最短路（用Dijkstra算法），该路记为P・将P加入G（相当于在G中又适当增加了一些边），构成新的图，新图必为欧拉图，用（1）的方法求出一个欧拉路作为行进路线即可。（3）G的奇次顶点个数大于2因任何一个图的奇次顶点个数必是偶数，故可将奇次顶点两两配对。我们的目标是：适当配对，使得每对顶点之间的最短路长之和达到最小。将这些路加入G构成新欧拉图，用（1）的方法求出一个欧拉路作为行进路线即可。例：求最佳邮递路线，G（V,E）,V={V1>V2>川9},v1v2（4）,v1v7（
5、1）,v2v3（2）^4（5）川2乃⑵®4⑴〉V4V5（1）*4沟（3）*4%（8）川5*（1°）*6巾（1）川?也（9），r={v7v9（6）,v8v9（3）}解：4个顶点{"宀川8*9}是奇次，先求他们z间的最短路^(v4,v7)=V4v3v2v7,C2?(v4>v7)=5^(v4>v8)=v4v8>^(v4,v8)=3^(V4>V9)=6^(v7,v8)=9^(V7>V9)=6d(v8>v9)=3^(v4>v9)=v4v8v9>^(v7,v8)=v7v8>^(v7,v9)=v7v9,^(v8,v9)=v8v9,再求这4个点之间的最佳配对，当4与7配对、8与9配对时，距离之和达到最小5+3
6、=8.在G中添加路径V4V3V2V?与冷沟，形成一个欧拉图，该图的任意一条欧拉路都是最佳邮递路线。题：求最佳邮递路线44232333113233231.推销员问题流动推销员需要访问某地区的所有城镇，最后回到出发点•问如何安排旅行路线使总行程最小.这就是推销员问题最佳推销员回路问题解法：由给定的图G=(V,E)构造一个以V为顶点集的完备图Gr二(UQ),Er的每条边(x,y)的权等于顶点x与y在图中最短路的权.例对一个完备图，用二边逐次修正法求】佳推销员回路(见文件“第9讲行遍性问题・ppt”)clearn=6;bbb=0;a二[0,56,35,2,51,60;0,0,21,57,78,70;0
7、,0,0,36,6&68;0,0,0,0,51,61;0,0,0,0,0,130,0,0,0,0,0];fori二2:nforj=l:i~la(i,j)=a(j,i);endenda(n,n+l)=a(n,1);b=a;cx二1:n+1;cxl=l:n+1;whilebbb==0bbb=l;forj=3:nfori=l:j-2ifa(i,i+l)+a(j,j+l)>a(i,j)+a(i+l,j+1
