(最新整理)第三章欧拉图和哈密顿图

1、(完整)第三章 欧拉图和哈密顿图(完整)第三章 欧拉图和哈密顿图 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)第三章 欧拉图和哈密顿图）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)第三章 欧拉图和哈密顿图的全部内容。16第三章 欧拉图与哈密顿图(七桥问题与一笔画,欧拉图与哈密顿图）教学安排的说明章节题

2、目：3.1环路;3.2 欧拉图；3.3 哈密顿图学时分配：共2课时本章教学目的与要求:认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别其它：由于欧拉图与一笔画问题密切相关,因此本章首先从一笔画问题讲起，章节内容与教材有所不同。课 堂 教 学 方 案课程名称：3.1环路;3。2欧拉图；3。3哈密顿图授课时数:2学时授课类型：理论课教学方法与手段：讲授法教学目的与要求:认识七桥问题的实质，理解一笔画问题的解决方法，会正确理解关于欧拉图和哈密顿图的判断定理，并进行识别教学重点、难点：（1） 理解环路的概念； （2） 掌握欧拉图存在的充分必要条件； （

3、3） 理解哈密顿图的一些充分和必要条件；教学内容：看图1，有点像“回”字，能不能从某一点出发，不重复地一笔把它画出来?这就是中国民间古老的一笔画游戏,而这个图形实际上也是来源于生活.中国古代量米用的“斗”?上下都是四方的，底小口大，从上往下看就是这样的图形。这类“一笔画”问题中最著名的当属“哥尼斯堡七桥问题了。一、问题的提出 图1哥尼斯堡七桥问题。18世纪，哥尼斯堡为东普鲁士的首府，有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图2（1），当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥,最后回到出发点。1735年，一群执着好奇的大学生写信请教当时正在圣彼得堡科学院担

4、任教授的著名数学家欧拉。欧拉通过数学抽象成功地解决了这一问题。欧拉发现欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于提出的“位置几何”.欧拉想到,岛与河岸陆地仅是桥梁的连接地点和通往地点,桥仅是从一地通往另一地的路径，一次能否不重复走遍七桥与河岸陆地大小是没有本质联系的，与桥的宽窄也是没有关系的。所以,相对问题而言,可舍弃之，而仅考虑与问题有密切联系的本质特征：岛和岸地可以是仅有位置而没有大小的“点”，桥梁可以是仅有连接作用而没有宽窄的连接两点的线，那么可以把这四处地点用a，b，c,d四个点来表示,同时将七座桥表示成连结其中两点的七条线，就

5、得到这样一张图于是，欧拉建立了一个数学模型，一个人不重复地走遍所有的七座桥,就相当于从图中某一点出发，不重复地一笔画出图来这样，“七桥问题”就转化为“一笔画”问题了。欧拉注意到，如果一个图能一笔画成,那么一定有一个起点开始画，也有一个终点.图上其它的点是“过路点”-画的时候要经过它。 这些点有什么特征呢？先来看看“过路点，它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点，不可能是有进无出，如果有进无出,它就是终点，也不可能有出无进，如果有出无进，它就是起点。因此,在“过路点”进出的边总数应该是偶数。 如果起点和终点是同一点,那么它也是属于“有进有出”的点，因此必须连着偶数条边，

6、这样图上所有点都连偶数条边。 如果起点和终点不是同一点，那么这两点连有奇数条边，这也是图中仅有的连着奇数条边的点。 现在对照七桥问题的图，b点连有3条边，a点连有5条边，c点d点各连3条边，哥尼斯堡七桥问题就变成了图2（2)中，是否存在经过每条边一次且仅一次,经过所有的顶点的闭链问题了.所以欧拉得出的结论是这个图肯定不能一笔画成，也就是说要想不重复的走遍这七座桥是不可能的。1736年瑞士数学家欧拉（euler）发表了图论的第一篇 论文“哥尼斯堡七桥问题”。欧拉在论文中指出，这样的闭链是不存在的。图2欧拉解决问题的关键是两步，先从实际问题中抽象出形式结构，再对形式结构进一步分析，抽象出其本质数量

7、特征,由此得出判别准则,问题获得答案.哥尼斯堡七桥问题的解决远远超出了它的娱乐价值，欧拉用了最简单的图形-点和线，把一个实际问题抽象成数学问题,巧妙地彻底解决了“七桥问题”.这充分显示了数学抽象的形式化和量化特征。由此提出的新思想开辟了数学的一个新的领域-图论,同时也为拓扑学的研究提供了一个初等的例子。此后许多著名的数学游戏成为图论和拓扑学发展的催化剂和导引，如哈密顿问题（绕行世界问题)、 四色猜想等。直到20世纪中期，这两门学科才逐步完善并迅速发展。二、欧拉图 定义1给定图g=v，e，通过g中的每一条边一次且恰好一次的闭链,称为欧拉闭链。存在欧拉闭链的图称为欧拉图。欧拉图另一定义:如果图g的

8、所有点均为偶数,则称图g为欧拉图。实际上，在图中，如果所有的边可以排起来而不重复，则该图为一链，或者是开链,或者是闭链,当是开链时，链中的点为偶数度,起点和终点皆为奇数度。当是闭链时，链中的点皆为偶数度。定理1：无向图g为欧拉图当且仅当g连通，并且所有顶点的度都是偶数. 证明:设g为一欧拉图，那么g显然是连通的。另一方面，由于g本身为一闭路径，它每经过一个顶点一次，便给这一顶点增加度数2，因而各顶点的度均为该路径经历此顶点的次数的两倍,从而均为偶数。反之，设g连通，且每个顶点的度均为偶数，欲证g为一欧拉图。为此，对g的边数归纳。当m = 1时，g必定为顶点的环，如图3（a)所示，显然这时g为欧

9、拉图。设边数少于m的连通图，在顶点度均为偶数时必为欧拉图,现考虑有m条边的图g。设想从g的任一点出发,沿着边构画，使笔不离开图且不在构画过的边上重新构画.由于每个顶点都是偶数度，笔在进入一个顶点后总能离开那个顶点，除非笔回到了起点。在笔回到起点时，它构画出一条闭路径，记为h。从图g中删去h的所有边，所得图记为g，g未必连通，但其各顶点的度数仍均为偶数（为什么？)。考虑g的各连通分支，由于它们都连通，顶点度数均为偶数，而边数均小于m,因此据归纳假设，它们都是欧拉图。此外，由于g连通，它们都与h共有一个或若干个公共顶点(如图3（b）所示），因此,它们与h一起构成一个闭路径.这就是说，g是一个欧拉图

10、。 （a） （b) 图3三、一笔画问题。要求笔不离纸，而且每条线只画一次，不准重复。显然哥尼斯堡七桥问题是一笔画问题。对于图来说，如果全部边(或有向边）可以排成一条链，则称这个图为一个一笔画.下列图形能否一笔画成?图4定理2设g是无向连通图,则g是一笔画g中只有0或2个奇数度顶点(他们分别是起点和终点）。即： 一笔画证明：设的链是点边序列，其中顶点可能重复，但边不重复。 对于任一非端点顶点，在欧拉路中每当出现一次,必关联两条边,故虽可重复出现，但是必是偶数。对于端点，若，则必是偶数，即中无奇数度顶点 .若 ，则必是奇数，必是奇数，即中有两个奇数度顶点 。上述定理的逆定理也成立，即：定理3：设g

11、是无向连通图， g中只有0或2个奇数度顶点g是一笔画。此定理分两步证：奇数度顶点是0，奇数度顶点是2.证明思路：只证明奇数度顶点是0 的情形，（证明过程给出了一种构造方法） （1）首先证明任取中点，必存在包含的圈。由于中点为偶数度,则从其中一个顶点开始构造一条圈,即从出发经关联边进入,则必可由再经关联边进入,如此下去,每边仅取一次，必存在到达的圈，(否则便与中点为偶数度矛盾) （2）若p： 通过了的所有边, p： 就是一条闭链. (3）否则，若中去掉p： 后得到子图,则中每个顶点度数都为偶数,因为原来的图是连通的,故p: 与至少有一个顶点重合,在中由出发重复(1)的方法，得到闭链l。 （4）当

12、p与l组合,若恰是，得欧拉路，否则重复（3),可得闭链m，依此类推可得一条欧拉路。奇数度顶点是2的情形可类似证明。因此，定理2与3可总结为设g是无向连通图， g中只有0或2个奇数度顶点g是一笔画。例1：下列图5中各图是否可以一笔画出?图5解：（1)有 个奇度顶点，无欧拉闭链或通路，不能一笔画成。（2)与（3）都是 个奇度顶点，其余均为偶度顶点，具有欧拉通路,可一笔画成。(4）均为偶度顶点,具有欧拉通路,可一笔画成。例2、“两只蚂蚁比赛问题”。两只蚂蚁甲、乙分别处在图 6左图中的顶点 处,并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点 处。如果它们速度相同，

13、问谁最先到达目的地?解：图 中，有两个奇度顶点 ，因此存在从 到 的开链,蚂蚁乙走到只要走一条欧拉通路，边数为 ，而蚂蚁甲要想走完图中所有边到达 ,至少要先一条边到达 ,再走一条欧拉通路，故它至少要走 条边到达 ,所以乙必胜.例3:甲乙两个邮递员去送信,两人以同样的速度走遍所有的街道，甲从a点出发，乙从b点出发，最后都回到邮局（c点）。如果要选择最短的线路,谁先回到邮局?图中a，c为奇点，其余都是偶点。甲从a点出发，可以不重复到达c点。乙从b出发一定会走重复的路，所以甲先回到邮局。例4图6右图是一个公园的平面图，能不能使游人走遍每一条路不重复？入口和出口又应设在哪儿?h点和b点是奇点，其余都是

14、偶点，所以入后和出口应设在h点和b点。 图6四、中国邮递员问题 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题 用图论的述语，在一个连通的赋权图g(v，e）中，要寻找一条闭链，使该闭链包含g中的每条边至少一次，且该闭链的权数最小也就是说要从包含g的每条边的闭链中找一条权数最小的闭链 如果g是欧拉图,则很容易由弗罗莱算法求出一个欧拉闭链，但是若g不是欧拉图，即存

15、在奇度数的顶点，则中国由递员问题的解决要困难得多本节的主要目标是给出在有奇度数顶点的连通图中寻找最小权数的闭链的方法 首先注意到，若图g有奇数度顶点，则g的奇数度顶点必是偶数个把奇数度顶点分为若干对,每对顶点之间在g中有相应的最短路，将这些最短路画在一起构成一个附加的边子集令g/ =g+e/，即把附加边子集e/ 叠加在原图g上形成一个多重图g/，这时g/中连接两个顶点之间的边不止一条显然g/是一个欧拉图，因而可以求出g/的欧拉闭链该欧拉闭链不仅通过原图g中每条边，同时还通过e/ 中的每条边，且均仅一次邮递员问题的难点在于当g的奇数度顶点较多时，可能有很多种配对方法,应怎样选择配对，能使相应的附

16、加边子集e/ 的权数(e/ ）为最小?为此有下列定理 定理 4 设g（v,e）为一个连通的赋权图，则使附加边子集e/ 的权数（e/ )为最小的充分必要条件是g+e/ 中任意边至多重复一次，且g+e/ 中的任意闭链中重复边的权数之和不大于该闭链总权数的一半 证明： 必要性用反证法设存在一种奇顶点集的配对，使其附加边子集e/ 权数 （e/ ）为最小若 g+e/ 中有一条边重复次，由于g+e/为欧拉图，所以删去相应的二次重复边后仍为欧拉图这样，相应的附加边子集的权数将减小,这与 （e/)为最小的假设矛盾这说明e/中的边均互不相同 其次,若g+e/ 中存在一个闭链，使它的重复边的权数之和大于该闭链总权

17、数的一半,则在e/ 中删去这些重复边（注意：这些边均在e/中），而代之以该闭链的其余部分的边再重复一次经过这种替代后所得到的边子集e/仍为附加子集,且（e/）（e/），又产生矛盾 充分性设有两个附加边子集e/和e/，均使g+e/和g+e/中每条边至多重复一次，且每个闭链中的重复边的权数和不大该闭链权数的一半，我们来证明（e/）=(e/)首先注意到，由e/和e/不相同的部分组成的图（记为）是由一个或若干个欧拉子图所组成的这是因为e/e/中每个顶点的度数均为偶数，而e/和e/的公共边数也是偶数,故中每个顶点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成 的任何

18、闭链都由e/和e/中的边组成，而e/和e/在闭链中的权数分别不大于该闭链权数的一半,因而任何闭链中属于e/中的权数之和与属于e/中的边数之和必定相等，所以(e/)=(e/)它就是最优附加边子集的权数，即e/和e/均为使附加边子集的权数达到最小的最优附加边子集 由定理4可得一个寻找邮递员问题最优解的方法现举例如下：例5已知邮递员要投递的街道如图7左图所示,试求最优邮路图7 解 先找出奇顶点：a1，a2，a3，a4，b1,b2，b3，b4奇顶点进行配对，不妨把a1与b1，a2与b2，a3与b3，a4与b4配对，求其最短路显然它不是最优解下面我们根据定理4来进行调解第一次调整:删去多于一条的重复边，

19、即a3与b3，a4与b4中的（a4，b3）调整后，实际上成为a1与b1，a2与b2，a3与a4，b3与b4的配对,它们的最短路如图7右图所示第二次调整:发现在闭链a1，a2，b2，a4,b3，b4，b1,a1中重复边的权数和为11，大于该闭链权数20的一半因而调整时，把该闭链的重复边删去，代之以重复其余部分,得图8左图可以看出，实际上是调整为a1与a2，b1与b4，a3与a4,b2与b3配对图8第三次调整：在图8左图中发现闭链 a3，a4,b2,a3中重复边的权数和为7，大于该闭链权数10的一半，因而删去原重复边（a3，v2，a4)和（a4，b2），而添加（b2，a3)，得到图8右图进行检查发

20、现，既没有多于一条的重复边，也没有任何闭链使其重复边的权数之和大于该闭链的一半,因此图8右图就是最优的附加边子集e/，而g+e/为欧拉图,可由弗罗莱算法找出最优邮路在现实生活中,很多问题都可以转化为中国邮递员问题，例如道路清扫时如何使开空车的总时间最少的问题等等上面例1题所用的求最优邮路的方法叫“奇偶点图上作业法”因为此方法要验证每个闭链，很不方便，edmods和johnson在1973年提出一种比较有效的方法，有兴趣的读者可参考有关资料例11.24 中国邮路问题 中国邮路问题是我国数学家管梅谷先生在20世纪60年代提出来的.该问题描述如下：一个邮递员从邮局出发，到所管辖的街道投递邮件,最后返

21、回邮局,若必须走遍所辖各街道中每一条至少一次,则怎样选择投递路线使所走的路程最短？ 下面用图论的语言来描述：用图论的语言来描述，即在一个带权图g中,能否找到一条回路c，使c包含g的每条边最少一次且c的长度最短？ 该问题求解思路大体包括三个方面： 1) 若g没有奇数度结点，则g是欧拉图，于是欧拉回路c是唯一的最小长度的投递路线。 2） 若g恰有两个奇数度结点vi和vj，则g具有欧拉迹,且邮局位于结点vi，则邮递员走遍所有的街道一次到达结点vj；从vj返回vi可选择其间的一条最短路径。这样，最短邮路问题转化为求vi到vj的欧拉迹和vj到vi的最短通路问题。 3) 若g中奇数度结点数多于2，则回路中

22、必须增加更多的重复边（路径)。这时，怎样使重复边的总长度最小？已有定理给出了判定条件，读者若有兴趣则请查阅相关文献。 五、哈密顿图 a(甲)b(乙)c哈密顿图的理论是著名的货郎担问题的源头。哈密顿图起源于一种游戏，它是由英国数学家哈密顿 于1859年提出的“周游世界游戏，它用一个正十二面体的20个顶点代替20个城市（图9（1），这个正十二面体同构于一个平面图(图9(2),要求沿着正十二面体的棱，从一个城市出发,经过每个城市恰好一次，然后回到出发点，这个游戏曾风靡一时,它有若干个解,称为哈密顿图。 图9这个游戏扩展到一般的图上就是：给定一个图，是否能找到一个环，它通过图g的每个结点一次且仅一次？

23、 哈密尔顿的十二面体图上存在一条哈密尔顿环，按照结点编号的顺序:12320-1.与欧拉图不同,确定一个图是否为哈密尔顿图是很困难的，目前还不存在有效的算法。但许多哈密尔顿图的充分条件都被证明,这里介绍其中的两个，其证明过程具有较好的示范意义，而且在研究哈密尔顿图的性质中得到了广泛的应用。图10.31定义2：给定图，若存在一条路经过图中的每个顶点恰好一次,这条路称作哈密顿路(hamilton walk)。若存在一条圈经过图中的每个顶点恰好一次 ,称作哈密顿圈,具有哈密顿圈的图称为哈密顿图（ hamilton graph）。 注意哈密顿图、哈密顿通路与欧拉图、欧拉路径之间的区别。它们之间几乎没有什

24、么联系。有的图既是哈密顿图又是欧拉图,有的图只是哈密顿图不是欧拉图，有的图只是欧拉图不是哈密顿图,有的图则两者皆非。特别要留意的是， 哈密顿图并不要求其哈密顿回路遍历图的所有的边，仅仅要求遍历图的所有的顶点。例6、判断下图是否具有哈密顿闭链，通路.图10解：(1） 存在哈密顿通路,但不存在哈密顿闭链。（2) 是哈密顿图，存在哈密顿闭链和通路。（3） 不存在哈密顿闭链，也不存在哈密顿通路。哈密顿图的判定虽然至今尚未找到一个像欧拉图的充要条件那样的“非平凡的”（不是定义的同义反复）关于哈密顿图、哈密顿通路的充分必要条件,但关于它们的充分性和必要性分别有一些研究成果。简单现介绍如下定理5：若图具有哈

25、密顿圈，则对于顶点集的每个非空子集均有成立。其中是中连通分支数.（该定理用于证明某些图不是哈密顿图） 证明思路:链c删1个顶点变成路，但仍连通，删2个顶点至多增加1个分支(删端点处的顶点不增加分支），依此类推。所以，增加的分支数不大于删除的顶点数|s|. 定理6：设图具有n个顶点的简单图，如果中每一对顶点度数之和大于等于n1,则中存在一条哈密顿路。 证明思路:1） 先证连通: 若有两个或多个互不连通的分支,设一个分图有个顶点,任取一个顶点,另一分图有个顶点，任取一个顶点,因为：, ， 与假设矛盾, 是连通的。 2） 先证（构造)要求的哈密顿路存在: 设中有p1条边的路,pn，它的顶点序列为。如

26、果有或邻接于不在这条路上的一个顶点，立刻扩展该路，使它包含这个顶点,从而得到p条边的路。否则和都只邻接于这条路上的顶点,我们证明在这种情况下,存在一条链包含顶点。 若邻接于,则即为所求。 若邻接于顶点集中之一， ,如果是邻接于， ,， ， ， 中之一，譬如是,则 是所求链。 如果不邻接于， ,， , , 中任一个，则最多邻接于pk-1个顶点, ， ，故，即与 度数之和最多为n-2，得到矛盾。 至此,已经构造出一条包含顶点的链,因为是连通的，所以在中必有一个不属于该链的顶点与链中某一顶点邻接,于是就得到一条包含p条边的链，重复前述构造方法,直到得到n1条边的路. 定理7：设图具有n个顶点的简单图

27、,如果中每一对顶点度数之和大于等于n,则中存在一条哈密顿链。 证明思路：由定理6知,必有一条哈密顿路，设为,若与邻接,则定理得证。 若与不邻接,假设邻接于， 2i,jn1, 必邻接于中之一。若不邻接于中之一,则至多邻接于n-k1个顶点,因而, ， , ,与假设矛盾， 所以必有一条哈密顿路注：利用以上定理不难明白: （1）顶点数目不少于3的完全图都是哈密顿图。 （2）每个顶点度数均不小于n/2的图，特别地,k正则图在kn/2时都是哈密顿图（n为图的顶点数）。 注意，定理7给出的条件只是充分条件，不是必要条件。例如，形如六边形的图显然是哈密顿图,但它的任意两个顶点的度数和都是4,小于n 1 = 5

28、 。例题7考虑在七天内安排七门课程的考试,使得同一位教师所任的两门课程不排在接连的两天中,试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的. 证明：设是具有七个顶点的图，每个顶点对应于一门课程考试,如果这两个顶点对应的课程考试是由不同教师担任的，那么这两个顶点之间有一条边,因为每个教师所担任课程数不超过4,故每个顶点的度数至少是3，任两个顶点的度数之和至少是6,故总是包含一条汗密尔顿路,它对应于一个七门考试课目的一个适当的安排. 定义3 给定图g=v，e具有n个顶点，如果将图g中度数之和至少是n的非邻接顶点联结起来得图g，对g重复上述步骤,直到不再有这样的顶点对存在为止，

29、所得的图,称为是原图g的闭包,记为c(g)。 定理8 当且仅当一个简单图的闭包是哈密顿图时，这个简单图是哈密顿图。 例8试构造满足下列条件的图g (1）g是欧拉图又是哈密顿图。 （2）g是欧拉图但不是哈密顿图。 （3）g是哈密顿图,但不是欧拉图。 （4）g既不是欧拉图也不是哈密顿图。解： 图11 例9在图12中，哪些是欧拉图？哪些是哈密顿图？哪些是平面图？ h h h h h h h h h h h hh h h h h hh h (4) h hh h h h h h (3) hh h h hh h h h h (5)图12例10在下列两图中各求一条哈密顿回路。 图13解:我们将图中顶点依次编号,按1，2，3,4，5，6，7，8，9，10的顺序在图中沿边旅行，就得到一条哈密顿回路。 哈密尔顿图具有很好的应