§6.5Euler图与Hamilton图的应用.docVIP

-PAGE 46- -PAGE 45- §6.5 Euler图和Hamilton图 5.1 基本概念 定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。 直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。 定理1 （ = 1 \* roman i）是Euler图的充分必要条件是连通且每顶点皆偶次。 （ = 2 \* roman ii）是Euler图的充分必要条件是连通且，是圈，。 （ = 3 \* roman iii）中有Euler迹的充要条件是连通且至多有两个奇次点。 定义 包含的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或圈；含Hamilton圈的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。 5.2 Euler回路的Fleury算法 1921年，Fleury给出下面的求Euler回路的算法。 Fleury算法： 1o. ，令。 2o. 假设迹已经选定，那么按下述方法从中选取边： （ = 1 \* roman i）和相关联； （ = 2 \* roman ii）除非没有别的边可选择，否则不是的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。 3o. 当第2步不能再执行时，算法停止。 5.3 应用 5.3.1 邮递员问题 中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。 上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。 显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。 对于非Euler图，1973年，Edmonds和Johnson给出下面的解法： 设是连通赋权图。 （ = 1 \* roman i）求。 （ = 2 \* roman ii）对每对顶点，求（是与的距离，可用Floyd算法求得）。 （ = 3 \* roman iii）构造完全赋权图，以为顶点集，以为边的权。 （ = 4 \* roman iv）求中权之和最小的完美对集。 （ = 5 \* roman v）求中边的端点之间的在中的最短轨。 （ = 6 \* roman vi）在（ = 5 \* roman v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。 （ = 7 \* roman vii）在（ = 6 \* roman vi）中得的图上求Euler回路即为中国邮递员问题的解。 多邮递员问题： 邮局有位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。 kPP的数学模型如下： 是连通图，，求的回路，使得 （ = 1 \* roman i），， （ = 2 \* roman ii）， （ = 3 \* roman iii） 5.3.2 旅行商（TSP）问题 一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。 一个可行的办法是首先求一个Hamilton圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈。 （ = 1 \* roman i）对于，构造新的Hamilton圈: , 它是由中删去边和，添加边和而得到的。若，则以代替，叫做的改良圈。 （ = 2 \* roman ii）转（ = 1 \* roman i），直至无法改进，停止。 用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。 这个算法的优劣程度有时能用Kruskal算法加以说明。假设是中的最优圈。则对于任何顶点，是在中的Hamilton轨，因而也是的生成树。由此推知：若是中的最优树，同时和是和关联的两条边，并使得尽可能