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