下载文档原格式
第二节欧拉图和哈密尔顿回路
一、欧拉图
欧拉（Euler）在1736年发表的关于图论方面的第一篇论文，解决了一个著名问题，称为哥尼斯堡七桥问题，从而使他成为图论的创始人。
问题是这样的：十八世纪的德国有座哥尼斯堡城，在流贯全城的普格尔河两岩和河中两个岛之间架设了七座桥，如图6.10（a）所示。
当时那里的居民热衷于这样一个游戏，即一个散步者能否从任一陆地出发，走过每座桥一次且仅走过一次，最后回到原地。
问题乍看起来很简单，但当时谁也不明白为什么没有人能够成功。
为了弄清这个问题，欧拉将每一块陆地用一顶点表示，每一座桥用连接相应的两个顶点的连线（即边）来代替，从而得到一个“图”（图 6.10（b））。
这个“图”使问题变得简洁明了。
直观上不难发现，为了能回到原来的陆地，要求与每个顶点（陆地）相关联的边数是偶数，这样才能保证从一条边出去，从另一条边回来。
由于在图6.10（b）中，与四个顶点相连的边数都是奇数，因而不可能
自任一顶点出发过每条边一次且仅一次而回到原地。
（a）图6.10（b）欧拉并不限于处理这个特殊事例，他推广了这个问题，提出并证明了下述定理。
定义1 在连通无向图G中，若存在经过每条边恰好一次的一个圈或一条链，就称此圈或链为欧拉圈或欧拉链。
或图G含一条欧拉圈，则称它为欧拉图。
显然，欧拉圈或欧拉链都可“一笔画出”；反之，若一个图能一笔画出，则它必然是欧拉圈或欧拉链。
定理1连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。
事实上，若G是欧拉图，C是其欧拉圈，则由定义，C包含G的所有边，由于图连通，故亦包含所有顶点。
C是任一中间顶点每出现一次，必与两条不同的边相关联，另因C的起点也是终点，故所有顶点都是偶次顶点。
定理2 连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。
上述定理提供了判断一笔画问题的准则：若连通无向图G无奇次顶点，则可由任一点起一笔画成并回到起点；若有两个奇次顶点，则由一奇次顶点起到另一奇次顶点终可一笔画成。
为能将一个图一笔画下去，当去掉已画出部分时，乘下的部分不应成为不连通图。
二、哈密尔顿回路
1859年英国数学家哈密尔顿（Hamilton）提出了一种名为周游世界的游戏。
他用一个正十二面体的二十个顶点（参见图6.11），代表二十个大城市，要求沿着棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。
为了解答这个问题，现绘制一个如图6.12所示的平面图，它与图6.11所示的十二面体图同构。
由图6.12中粗线边组成的圈，符合哈密尔顿提出的要求，所以它是这个问题的一个解，需指出的是这个问题的解还不止一个。
如果不要求最后回到出发点，那么，解就更多了。
在一个图中，如果有一条链（圈）经过每个顶点恰好一次，那么这条链（圈）就称为哈密尔顿链（圈）。
表面上，哈密尔顿问题与欧拉问题很相似，但实际上，两者迥不同。
前者指的是过每个顶点恰好一次的回路，而后者说的是过每边恰好一次的圈。
用定理1很容易判断一个图是否为欧拉图，而求解哈密尔顿回路，迄今还没有比较简单的通用方法。
图6.11 图6.12
哈密尔顿回路是图论的重要课题之一，它具有重要的实际意义。
著名的旅行推销员问题（或称货郎担问题），就是要求出总路程最短的哈密尔顿回路。
三、中国邮路问题
某邮递员从邮局出发，走过每条街道至少一次去投递邮件，最后回到邮局，他应走什么样的路线才能使所走的总路程最短？这个问题是我国管梅谷教授于1962年首先研究的，国际上通称为中国邮路问题。
在邮递员服务范围的街道图上标明各条街的路长，就构成了一连通赋权图G。
若G无奇次顶点，根据定理1，G就是欧拉图，因每边仅过一次，故总权是最小的。
若G有奇次顶点，则它就不是欧拉图，然而题设条件是要求过每边至少一次，并未限制只许一次，故总可以在这些奇次顶点上添加一些与原图的边相重复的边，使这些奇次顶点成为偶次顶点，从而得到一个将重复边看成是另一条新边的欧拉图。
现在的问题是这些重复边如何添加，才能得到一个总权（总路长）最小的欧拉图。
定理3使图G成为总权最小的欧拉图的充要条件是：
（1）在有奇次顶点的图G中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。
（2）在图G 的每个回路上，重复边之总权不超过该回路非重复边之总权。
根据以前的分析，本定理是显然的。
例1 试为图6.13（a ）构成总权最小的欧拉图，图中线旁的数字为相应边的权。
（a ） （b ）
图6.13
解 因顶点①和③为奇次，要使成欧拉图，需用加重复边的方法使这两个顶点变为偶次。
最易想到的作法是在边)3,1(e （即在顶点①与③之间）上加重复边，将其变为欧拉图。
但由于在回路（1，3，4）中)3,1(e 的权大于该回路总权（等于
7）的一半，故这样得到的欧拉图不是总权最小的欧拉图。
如在边)4,1(e 和)4,3(e 上加重复边（图6.13（b ）），则可满足定理3的要求，从而得总权最小的欧拉图（总权等于15）。
通过难于一次找到总权最小的欧拉图，这时可通过对欧拉图的逐步调整达到总权极小化，即对每一回路进行检查，不满足定理3时就调整重复边，但在该过程中始终保持各顶点的次数为偶数。
例2 试为图6.14（a ）所示的街道规划最优投递路线。
解 可按以上所述步骤进行，最终结果示于图6.14（b ），总权等于52，重复边的长度等于10。
（a ） （b ）
图6.14
四、旅行售货员问题
一个旅行售货员想去某些城镇售货，然后再回到他的出发地。
各城镇之间的路程是已知的，问应如何安排他的旅行路线，才能使他经过每个城镇恰好一次，且总路程最短。
用图论的术语来说，就是在一个加权图中，找出一条总权最小的哈密尔顿回路。
到目前为止，旅行售货员问题还没有有效的通用算法。
假如采用枚举法，售货员从城市i v 出发，去1v ，2v ，…，n v 城市售货，则有)!1(-n 种可能方案。
随着n 的增加，)!1(-n 的值迅速增加，例如当n =20时，)!1(-n =1.216×1710。
对这么多个方案逐个计算并比较，显然是不可能的。
下面介绍一种近似解法。
首先任取一条哈密尔顿回路，不失一般性，它经过的顶点序列为1v ，2v ，…，i v ，1+i v …，j v ，1+j v ，…，n v ，若对某一对顶点i v 和j v ，相应边权有如下关系：
),(),(11+++j i j i v v w v v w ＜),(),(11+++j j i i v v w v v w 则用边),(j i v v 和边),(11++j i v v
替换边),(1+i i v v 和边),(1+j j v v （参见图6.15），可
得另一哈密尔顿回路，其权更小。
用这种方法对
哈密尔顿回路进行若干次改进，即可获得比较好
的回路。
例3 用上述近似法对图6.16（a ）中的回 图6.15
路（1v ，2v ，3v ，4v ，5v ，6v ，1v ）进行改进。
图6.16
解 其各次改进方案示于图6.16（b ）、6.16（c ）和图6.16（d ）中。
图中各边旁的数字为该边的权，双线表示相应方案的哈密尔顿回路，图右下角括号内的数字为该回路的总权。
