《Euler图和Hamilton图实用教案》由会员分享，可在线阅读，更多相关《Euler图和Hamilton图实用教案（17页珍藏版）》请在金锄头文库上搜索。
1、 一、一、EulerEuler图和中图和中国国(zhnu)(zhnu)邮邮递员问题递员问题 经过(jnggu)图的每条边至少一次的闭迹称为图的环游；经过(jnggu)每条边仅一次的环游称为图的Euler环游。包含Euler环游的图称为Euler图。 1973年瑞典数学家欧拉解决的柯尼斯堡问题，实质就是在图中寻找一条(y tio)经过每条边一次且仅一次的闭迹，推广这个问题进行Euler图的研究。第1页/共16页第一页，共17页。定理一：当G是连通(lintng)图时，下面三个命题等价G是Euler图G的每个顶点是偶次G是圈的并，且圈的交集(jioj)是空集第2页/共16页第二页，共17页。 “一
2、笔画”，就是(jish)指一笔能画出的图形，容易知道，一笔画其实就是(jish)Euler通路和回路的思想。推论一：一个连通(lintng)图有Euler迹当且仅当最多有两个奇点。第3页/共16页第三页，共17页。中国中国(zhnu)(zhnu)邮递员问题邮递员问题 一位邮递员从邮局选好邮件去投递，然后(rnhu)回到邮局。他必须经过所管辖的街道至少一次，请问这位邮递员如何选择一条路线，使得所行路程尽可能的少。这就是中国邮递员的原始模型，是我国管梅谷教授1962年首先提出并开始研究的。 如果(rgu)G是Euler图，则任何环游都是最优环游，针对这种情形，Fleury提出一种算法，能在Eule
3、r图中找出环游。第4页/共16页第四页，共17页。FleuryFleury算法算法(sunf)(sunf)步骤步骤确定任意一个起点。若某条行迹已经确定，从E-e1,e2,ei中选择下一条边，满足 a。 ei+1与ei相邻 b。除非无选择余地，否则ei+1不是G=G- e1,e2,.ei的桥3. 直到步骤2不能进行(jnxng)为止。第5页/共16页第五页，共17页。二、【二、【FleuryFleury算法算法(sunf)(sunf)：见：见wordword文档】文档】第6页/共16页第六页，共17页。 三、三、HamiltonHamilton圈和圈和旅行旅行(lxng)(lxng)售货商问售货
4、商问题题 1859年，数学家Hamilton发明(fmng)了一种周游世界的游戏。把一个12面体的20个顶点分别标上北京、东京、华盛顿等20个大都市的名字，要求玩的人从某城市出发，沿着12面体的棱通过每一个城市恰好一次，再回到出发的城市。这种游戏在欧洲曾经风靡一时，Hamilton以25个金币的高价把该项专利卖给了一个玩具商。 用图论的语言来讲，此游戏(yux)本质就是在一个12面体上寻找经过每一个顶点一次且恰好一次的特殊的圈，即Hamilton回路。第7页/共16页第七页，共17页。 与欧拉图的情形相反，到目前为止，判断Hamilton圈非平凡的充分必要条件尚不清楚；事实上，这是图论尚未解决
5、(jiju)的主要问题之一。一名旅行售货员想去访问若干村，最后回到他的出发地。给定各村之间所需的旅行时间，应该怎样计划他的路线，使得这位售货员能对每个村进行一次访问而总时间最短？这个问题就是(jish)著名的旅行售货员问题，或者叫做货郎担问题。第8页/共16页第八页，共17页。 首先给出求近似(jn s)最优Hamilton圈的最邻近算法的基本思想： 针对旅行(lxng)售货商问题，给出较好的近似算法，即最临近算法和一个修改算法。设n个顶点的赋值完全图为G，W为权值矩阵。根据实际问题，可以假设w(uv)+w(vx)=w(ux). 结合图论知识，上述货郎担问题本质就是在赋权完全图中，找出一个最小
6、权的Hamilton圈，此圈称为最优圈。与最短路问题相反，至今尚未有求解旅行售货商问题的有效算法，因此，在这里只试图(sht)找出较好的解，但不一定是最优解。第9页/共16页第九页，共17页。任选一顶点V0为起点(qdin)，找一条与V0关联且权最小的边e1,e1的另一个顶点是V1.得一条路V0V1;若已选出路V0V1Vi,在剩下的点中选取一个与Vi最近的相邻点Vi+1得新的路；若i+1n-1,用i代替i+1，返回2； 否则，记C=V0V1VpV0.停止【最邻近(ln jn)算法思想】第10页/共16页第十页，共17页。 四、改良四、改良(giling)(giling)圈算法圈算法 假设已经找
7、到G的一个Hamilton圈V1V2VnV1. 对圈中所有满足1i+1jV的i,j，按照以下(yxi)方法寻找新的Hamilton圈。【算法(sun f)思想】1. 在圈中寻找i不等于j,使得ViVj,Vi+1,Vj+1在圈中，且W(ViVj)+W(Vi+1Vj+1)W(ViVi+1)+W(VjVj+1) 则构成新的圈.2. 用新圈代替旧圈，直至终止。第11页/共16页第十一页，共17页。【算法(sun f)的Matlab程序】见word文档第12页/共16页第十二页，共17页。例：给定四个点例：给定四个点(0,0),(100,1000),(0,2),(1000,0),(0,0),(100,1
8、000),(0,2),(1000,0),用用改良改良(giling)(giling)圈算法计算经过这四个点的圈算法计算经过这四个点的HamiltonHamilton圈。圈。V= 0 0 ;100 1000; 0 2; 1000 0For 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); endend第13页/共16页第十三页，共17页。第四讲习题：判断(pndun)图1是否是欧拉图，若是，求Euler回路。第14页/共16页第十四页，共17页。2.给定10个点的坐标(zubio)(5,67),(37,8),(4,97),(
9、200,9), (81,5),(4,50),(4,420),(250,381),(-3,40),(7,-64), 试用改良圈算法求通过这10个点的Hamilton圈。计算直接10个点顺序的圈的长度，并比较结果。第15页/共16页第十五页，共17页。感谢您的观看(gunkn)！第16页/共16页第十六页，共17页。内容(nirng)总结一、Euler图和中国邮递员问题。这就是中国邮递员的原始模型，是我国管梅谷教授1962年首先提出(t ch)并开始研究的。ei+1与ei相邻。除非无选择余地，否则ei+1不是G=G-。面体上寻找经过每一个顶点一次且恰好一次的特殊。首先给出求近似最优Hamilton圈的最邻近算法的基本思想：。V= 0 0。第15页/共16页。感谢您的观看第十七页，共17页。
