第4讲Euler图和Hamilton图

单击此处编辑母版标题样式,下,回,停,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,1. Euler,图和中国邮递员问题,2.,Fleury,算法,3. Hamilton,图和旅行售货商问题,第四讲,Euler,图和,Hamilton,图,4.,改良圈算法,一、,Euler,图和中国邮递员问题,经过图的每条边至少一次的闭迹称为图的,环游,；经过每条边仅一次的环游称为图的,Euler,环游,。包含,Euler,环游的图称为,Euler,图,。,1973,年瑞典数学家欧拉解决的柯尼斯堡问题，实质就是在图中寻找一条经过每条边一次且仅一次的闭迹，推广这个问题进行,Euler,图的研究。,定理一：当,G,是连通图时，下面三个命题等价,G,是,Euler,图,G,的每个顶点是偶次,G,是圈的并，且圈的交集是空集,“一笔画”，就是指一笔能画出的图形，容易知道，一笔画其实就是,Euler,通路和回路的思想。,推论一：一个连通图有,Euler,迹当且仅当最多有两个奇点。,中国邮递员问题,一位邮递员从邮局选好邮件去投递，然后回到邮局。他必须经过所管辖的街道至少一次，请问这位邮递员如何选择一条路线，使得所行路程尽可能的少。这就是中国邮递员的原始模型，是我国管梅谷教授,1962,年首先提出并开始研究的。,如果,G,是,Euler,图，则任何环游都是最优环游，针对这种情形，,Fleury,提出一种算法，能在,Euler,图中找出环游。,Fleury,算法步骤,确定任意一个起点。,若某条行迹已经确定，从,E-e,1,e,2,e,i,中选择下一条边，满足,a,。,e,i+1,与,e,i,相邻,b,。除非无选择余地，否则,e,i+1,不是,G=G-,e1,e2,.,ei,的桥,3.,直到步骤,2,不能进行为止。,二、,【,Fleury,算法：见,word,文档,】,三、,Hamilton,圈和,旅行售货商问题,1859,年，数学家,Hamilton,发明了一种周游世界的游戏。把一个,12,面体的,20,个顶点分别标上北京、东京、华盛顿等,20,个大都市的名字，要求玩的人从某城市出发，沿着,12,面体的棱通过每一个城市恰好一次，再回到出发的城市。这种游戏在欧洲曾经风靡一时，,Hamilton,以,25,个金币的高价把该项专利卖给了一个玩具商。,用图论的语言来讲，此游戏本质就是在一个,12,面体上寻找经过每一个顶点一次且恰好一次的特殊,的圈，即,Hamilton,回路。,与欧拉图的情形相反，到目前为止，判断,Hamilton,圈非平凡的充分必要条件尚不清楚；事实上，这是图论尚未解决的主要问题之一。,一名旅行售货员想去访问若干村，最后回到他的出发地。给定各村之间所需的旅行时间，应该怎样计划他的路线，使得这位售货员能对每个村进行一次访问而总时间最短？这个问题就是著名的旅行售货员问题，或者叫做货郎担问题。,首先给出求近似最优,Hamilton,圈的最邻近算法的基本思想：,针对旅行售货商问题，给出较好的近似算法，即最临近算法和一个修改算法。设,n,个顶点的赋值完全图为,G,，,W,为权值矩阵。根据实际问题，可以假设,w(uv)+w(vx,)=,w(ux,).,结合图论知识，上述货郎担问题本质就是在赋权完全图中，找出一个最小权的,Hamilton,圈，此圈称为最优圈。与最短路问题相反，至今尚未有求解旅行售货商问题的有效算法，因此，在这里只试图找出较好的解，但不一定是最优解。,任选一顶点,V,0,为起点，找一条与,V,0,关联且权最小的边,e1,e1,的另一个顶点是,V,1,.,得一条路,V,0,V,1,;,若已选出路,V,0,V,1,V,i,在剩下的点中选取一个与,V,i,最近的相邻点,V,i+1,得新的路；,若,i+1n-1,用,i,代替,i+1,，返回,2,；,否则，记,C=V,0,V,1,V,p,V,0,.,停止,【,最邻近算法思想,】,四、改良圈算法,假设已经找到,G,的一个,Hamilton,圈,V,1,V,2,V,n,V,1.,对圈中所有满足,1i+1jV,的,i,j,，按照以下方法寻找新的,Hamilton,圈。,【,算法思想,】,1.,在圈中寻找,i,不等于,j,使得,ViVj,Vi+1,Vj+1,在圈中，且,W(V,i,V,j,)+W(V,i,+1V,j+1,)W(V,i,V,i+1,)+W(V,j,V,j+1,),则构成新的圈,.,2.,用新圈代替旧圈，直至终止。,【,算法的,Matlab,程序,】,见,word,文档,例：给定四个点,(0,0),(100,1000),(0,2),(1000,0),用改良圈算法计算经过这四个点的,Hamilton,圈。,V= 0 0 ;100 1000; 0 2; 1000 0,For i=1,：,4,for j=1:4,W(i,j,)=sqrt(V(i,1)-V(j,1)2+(V(i,2)-V(j,2)2);,end,end,第四讲习题：,判断图,1,是否是欧拉图，若是，求,Euler,回路。,2.,给定,10,个点的坐标,(5,67),(37,8),(4,97),(200,9), (81,5),(4,50),(4,420),(250,381),(-3,40),(7,-64),试用改良圈算法求通过这,10,个点的,Hamilton,圈。计算直接,10,个点顺序的圈的长度，并比较结果。,