《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页。