§euler图和hamilton图的应用

《§euler图和hamilton图的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§6.5Euler图和Hamilton图5.1基本概念定义经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理1（i）是Euler图的充分必要条件是连通且每顶点皆偶次。（ii）是Euler图的充分必要条件是连通且，是圈，。（iii）中有Euler迹的充要条件是连通且至多有两个奇次点。定义包含的每个顶点的轨叫做Hamilton(哈密顿

2、)轨；闭的Hamilton轨叫做Hamilton圈或圈；含Hamilton圈的图叫做Hamilton图。直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。5.2Euler回路的Fleury算法1921年，Fleury给出下面的求Euler回路的算法。Fleury算法：1o.，令。2o.假设迹已经选定，那么按下述方法从中选取边：（i）和相关联；（ii）除非没有别的边可选择，否则不是的割边(cutedge)。(所谓割边是一条删除后使连通图不再

3、连通的边)。3o.当第2步不能再执行时，算法停止。5.3应用5.3.1邮递员问题中国邮递员问题一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：设是连通赋权图。（i）求。4

4、5/3（ii）对每对顶点，求（是与的距离，可用Floyd算法求得）。（iii）构造完全赋权图，以为顶点集，以为边的权。（iv）求中权之和最小的完美对集。（v）求中边的端点之间的在中的最短轨。（vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。（vii）在（vi）中得的图上求Euler回路即为中国邮递员问题的解。多邮递员问题：邮局有位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。kPP的数

5、学模型如下：是连通图，，求的回路，使得（i），，（ii），（iii）5.3.2旅行商（TSP）问题一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。一个可行的办法是首先求一个Hamilto

6、n圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈。（i）对于，构造新的Hamilton圈:,它是由中删去边和，添加边和而得到的。若，则以代替，叫做的改良圈。（ii）转（i），直至无法改进，停止。用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。45/3这个算法的优劣程度有时能用Kruskal算法加以说明。假设是中的最优圈。则对于任何顶点，是在中的Hamilton轨，因而也是的生成树。

7、由此推知：若是中的最优树，同时和是和关联的两条边，并使得尽可能小，则将是的一个下界。这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。例13从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161

8、Pe5178685113T607068611345/3