第三章哈密顿图

1、欢迎同学们！第三章第三章 欧拉图和哈密顿图欧拉图和哈密顿图欧拉（欧拉（L.Euler,1707.4.15- L.Euler,1707.4.15- 1783.9.181783.9.18）著名的数学家。）著名的数学家。生于瑞士的巴塞尔，卒于彼生于瑞士的巴塞尔，卒于彼得堡。大部分时间在俄国和得堡。大部分时间在俄国和德国度过。他早年在数学天德国度过。他早年在数学天才贝努里赏识下开始学习数才贝努里赏识下开始学习数学学, 17, 17岁获得硕士学位，毕岁获得硕士学位，毕业后研究数学业后研究数学, ,是数学史上最是数学史上最高产的作家。在世发表论文高产的作家。在世发表论文700700多篇多篇, ,去世后还留

2、下去世后还留下100100多多篇待发表。其论著几乎涉及篇待发表。其论著几乎涉及所有数学分支。所有数学分支。欧拉在数学、物理、天文、建筑以至音乐、哲欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领学方面都取得了辉煌的成就。在数学的各个领域，常常见到以欧来命名的公式、定理、和重域，常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如要常数。课本上常见的如、i、e、sin、cos、tg、x、f(x)等，都是他创立并推广的。欧等，都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论，拉还首先完成了月球绕地球运动的精确理论，创立了分析力学、刚体力学等力学学科

3、，深化创立了分析力学、刚体力学等力学学科，深化了望远镜、显微镜的设计计算理论。了望远镜、显微镜的设计计算理论。 第一部分第一部分 欧拉图欧拉图 1736年瑞士数学家欧拉发表了图论的第一篇年瑞士数学家欧拉发表了图论的第一篇著名论文著名论文“哥尼斯堡七桥问题哥尼斯堡七桥问题”(下称七桥问题下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生假日，有些城市居民进行环城周游，于是便产生了能否了能否“从某地出发，通过每桥恰好一次，在

4、走从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处遍了七桥后又返回到原处”的问题。的问题。 欧拉圈、欧拉图欧拉圈、欧拉图定义定义 图图G中的一圈，若它通过中的一圈，若它通过G中的每一条中的每一条边边(或弧或弧)恰好一次，则称该圈为欧拉圈，具恰好一次，则称该圈为欧拉圈，具有这种圈的图称为欧拉无向有这种圈的图称为欧拉无向(或有向或有向)图。图。定理定理1 无向图无向图G是欧拉图是欧拉图, 当且仅当当且仅当G是连通图是连通图, 且且G中中没有奇度顶点。没有奇度顶点。 证：设证：设G = 是含有是含有m条边的条边的n阶非平凡无向阶非平凡无向图图, 其中其中: V = v1, v2, , vn

5、。 1). 必要性必要性 因为因为G为欧拉图为欧拉图, 所以所以, G中存在欧拉圈。设中存在欧拉圈。设C是是G中中的欧拉圈的欧拉圈, vi, vj V, vi, vj都在都在C上上, 因此因此, vi和和vj是连是连通的通的, 所以所以, G为连通图。为连通图。 又又 vi V, vi在在C上每出现一次获得上每出现一次获得2度。若出现度。若出现k次就获得次就获得2k度度, 即即: d(vi) = 2k, 所以所以, G中无奇度顶点。中无奇度顶点。2). 充分性充分性由由G为非平凡的连通图可知为非平凡的连通图可知: G中边数中边数m 1。对。对m作归纳。作归纳。(1) m = 1时时, 由由G的

6、连通性和无奇度顶点可的连通性和无奇度顶点可知知: G只能是一个环只能是一个环, 因此因此, G为欧拉图。为欧拉图。(2) 设设m k(k 1)时时, 结论成立要证明结论成立要证明m = K+1时时, 结论也成立。结论也成立。 由由G的连通性和无奇度顶点可知的连通性和无奇度顶点可知: (G) 2。用扩大路径法可以证明。用扩大路径法可以证明G中存在长度大于中存在长度大于或等于或等于3的圈。的圈。 设设C为为G中一个圈中一个圈, 删除删除C上的全部边上的全部边, 得得G的生成子图的生成子图G。设。设G有有s个连通分支个连通分支G1, G2, , Gs, 每个连通分支至多有每个连通分支至多有k条边条边

7、, 且且无奇度顶点无奇度顶点, 并且设并且设Gi与与C的公共顶点为的公共顶点为vji*(i = 1.s)。由归纳假设可知由归纳假设可知: G1, G2, , Gs都是欧拉图都是欧拉图, 因此因此, 都存在欧拉圈都存在欧拉圈Ci(i = 1.s)。现在将现在将C还原还原(即将删除的边重新加上即将删除的边重新加上), 并从并从C上的某上的某顶点顶点vr开始进行遍历开始进行遍历, 每遇到每遇到vji*, 就行遍就行遍Gi中的欧拉圈中的欧拉圈Ci(i=1.s), 最后最后, 回到回到vr, 得圈得圈C”: vr vj1* vj1* vj2* vj2* vjs* vjs* vr。此圈此圈C”经过经过G中

8、每条边一次且仅一次。因此中每条边一次且仅一次。因此, C”是是G中的欧拉圈中的欧拉圈(如右下图所示如右下图所示)。故故, G为欧拉图。为欧拉图。定理定理2 2 连通图连通图G G具有欧拉路而无欧拉圈具有欧拉路而无欧拉圈, ,当且仅当当且仅当G G恰有两个奇数度顶点恰有两个奇数度顶点. .证证: :必要性必要性: :设连通图设连通图G G从顶点从顶点a a到顶点到顶点b b有欧拉路有欧拉路C,C,但不是欧拉圈但不是欧拉圈. .在欧拉路在欧拉路C C中中, ,除第一边和最后一除第一边和最后一边外边外,每经过每经过G G中顶点中顶点x xi i( (包括包括a a和和b),b),都为顶点都为顶点x

9、xi i贡献贡献2 2度度, ,而而C C的第一边为的第一边为a a贡献贡献1 1度度,C,C的最后一条的最后一条边为边为b b贡献贡献1 1度度. .因此因此,a,a和和b b的度数均为奇数的度数均为奇数, ,其余其余结点度数均为偶数结点度数均为偶数. . 充分性充分性:设连通图设连通图G恰有两个奇数度结点恰有两个奇数度结点,不妨设为不妨设为a和和b,在图在图G中添加一条边中添加一条边e=a,b得得G,则则G的每个结点的度数均为偶数的每个结点的度数均为偶数,因因而而G中存在欧拉圈中存在欧拉圈,故故G中必存在欧拉路中必存在欧拉路.凡是由偶点组成的连通图，一定可以一笔凡是由偶点组成的连通图，一定

10、可以一笔画成；画时可以任一偶点为起点，最后一定画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。能以这个点为终点画完此图。凡是只有两个奇点（其余均为偶点）的连凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。奇点为起点，另一个奇点为终点。其他情况的图，都不能一笔画出。其他情况的图，都不能一笔画出。“一笔划一笔划”问题问题 ？这是一些平面图形，请你思考图形能否一笔画出与什么有关？ 例例1 1 观察下面的图形，说明哪些图可以一笔画完，哪些能，为什观察下面的图形，说明哪些图可以一笔画完，哪些能，

11、为什么？对于可以一笔画的图形，指明画法么？对于可以一笔画的图形，指明画法 例例2 下图是国际奥委会的会下图是国际奥委会的会标，你能一笔把它画出来标，你能一笔把它画出来吗？吗？构造欧拉圈 思想：在画欧拉圈时，已经经过思想：在画欧拉圈时，已经经过的边不能再用。因此，在构造欧拉圈的边不能再用。因此，在构造欧拉圈过程中的任何时刻，假设将已经经过过程中的任何时刻，假设将已经经过的边删除，剩下的边必须仍在同一连的边删除，剩下的边必须仍在同一连通分支当中。通分支当中。设设G为欧拉图为欧拉图, 通常情况下通常情况下, G中存在若干条欧拉圈。中存在若干条欧拉圈。下面介绍一种求欧拉圈的算法。下面介绍一种求欧拉圈的

12、算法。1Fleury算法算法(1) 任取任取v0 V(G), 令令P0=v0(2) 设设Pi = v0e1v1e2eivi已经遍历已经遍历, 按下面方法从按下面方法从E(G) - e1, e2, , ei 中选取中选取ei+1:ei+1与与vi相关联相关联ei+1不应取不应取Gi = G - e1, e2, , ei 中的桥中的桥, 除非无其除非无其它边可供行遍它边可供行遍(3) 重复步骤重复步骤(2), 直到步骤直到步骤(2)不能再进行为止。不能再进行为止。可证明可证明: 当算法停止时当算法停止时, 所得简单圈所得简单圈Pm = v0e1v1 e2 emvm(vm=v0)为为G中一条欧拉圈。

13、中一条欧拉圈。关于一笔画问题的生活转化关于一笔画问题的生活转化1、甲乙两个邮递员去送信，两人以同样的速度走遍、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从所有的街道，甲从A点出发，乙从点出发，乙从B点出发，最后点出发，最后都回到邮局（都回到邮局（C点）。如果要选择最短的线路，谁点）。如果要选择最短的线路，谁先回到邮局？先回到邮局？DCEFB ADABCEFGHIJK 例例2 下图是一个公园的平面图下图是一个公园的平面图.要使游客走遍要使游客走遍每条路而不重复，问出入口应设在哪里？每条路而不重复，问出入口应设在哪里？甲甲A乙乙BC例例(蚂蚁比赛问题蚂蚁比赛问题) 甲、乙两只蚂蚁分别

14、位于如下图中的结点A，B处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？例例4 下图是某展览厅的平面图，它由五个展室下图是某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个出口，问游人能否一厅还有一个进口和一个出口，问游人能否一次不重复地穿过所有的门，并且从入口进，次不重复地穿过所有的门，并且从入口进，从出口出？从出口出？设计展览会参观路线设计展览会参观路线ABCJEFIKHGDLNMOABCIJDKLMNHOEGFH,G,O,

15、F,E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,HMHIEFJKGDABC一人如果从门一人如果从门M进入进入，再从再从门门K走出走出，他，他能否不重复地能否不重复地走过每一扇门？走过每一扇门？ 例例3 3 一张纸上画有如下图所示的图，你能否用剪刀一张纸上画有如下图所示的图，你能否用剪刀一次连续剪下图中的三个正方形和两个三角形？一次连续剪下图中的三个正方形和两个三角形？HABCDEFGM中国邮递员问题中国邮递员问题(Chinese Postman Problem, CPP)是由我是由我国管梅谷教授于国管梅谷教授于1962年首先提出并发表的年首先提出并发表的例如：观察下

16、列段道图例如：观察下列段道图 问题：从邮局出发，走遍邮区的所有街道至少一次再回到邮问题：从邮局出发，走遍邮区的所有街道至少一次再回到邮局，按照什么样的路线投递邮件才能使总的路程最短？局，按照什么样的路线投递邮件才能使总的路程最短？ 中国邮递员问题中国邮递员问题图图2图图1 数学模型：数学模型： 构造无向带权图构造无向带权图G，E（G）中每个元素对应）中每个元素对应于辖区内的一条街道，于辖区内的一条街道，V（G）中的元素对应于街）中的元素对应于街道的交叉点，街道长度用相应边的权表示。道的交叉点，街道长度用相应边的权表示。 则问题的解对应于则问题的解对应于G中包含所有边的权最小中包含所有边的权最小

17、的圈，称为最优圈的圈，称为最优圈(注意：未必是简单圈注意：未必是简单圈)。 当当G是欧拉图，则最优圈即欧拉圈。是欧拉图，则最优圈即欧拉圈。 若若G不是欧拉图，则通过加边来消除不是欧拉图，则通过加边来消除G中的中的奇度顶点，要求使加边得到的欧拉图奇度顶点，要求使加边得到的欧拉图G中重复边中重复边的权和最小。的权和最小。 C是带正权无向连通图是带正权无向连通图G中的最优圈当且仅当对中的最优圈当且仅当对应的欧拉图应的欧拉图G*满足：满足：(1) G的每条边在的每条边在G*至多重复一次；至多重复一次；(2) G的每个的每个(初级初级)圈在圈在G*重复边权的和不超过该圈重复边权的和不超过该圈权的一半。权

18、的一半。l算法过程算法过程1用用Dijstra算法求所有奇度顶点对之间的最短路径。算法求所有奇度顶点对之间的最短路径。(若若G是欧拉图，直接用是欧拉图，直接用Fleury算法算法)2以以G中所有奇度顶点构造带权完全图中所有奇度顶点构造带权完全图G2k, 每边的每边的权是两端点间最短路径长度。权是两端点间最短路径长度。3求求G2k中的最小权完美匹配中的最小权完美匹配M。4按照按照M中的各个路径添加重复边。中的各个路径添加重复边。 再用再用Fleury算算法求欧拉圈。法求欧拉圈。 3 5 5 4 8 14 6 10 9 1 2 6 2 1 1 2 5 3 4 2 欧拉圈欧拉圈 最理想的投递路线，就

19、是该段道图是一条欧拉圈。图（最理想的投递路线，就是该段道图是一条欧拉圈。图（2）的投递路线如下图（的投递路线如下图（3）。）。 含有奇点的段道图不能一笔画出，有些道路需要重复走两次含有奇点的段道图不能一笔画出，有些道路需要重复走两次的都要添上一条弧。图（的都要添上一条弧。图（1）添弧后如图（）添弧后如图（4）。）。 图图3图图4最优投递路线最优投递路线 重复的路最短重复的路最短 添弧的总长度最添弧的总长度最短短添弧最短的条件添弧最短的条件（1）没有重叠的添弧）没有重叠的添弧（2）每一个圈上添弧的总长度不超过圈长的一半）每一个圈上添弧的总长度不超过圈长的一半最短的一组添弧称为最优解。最短的一组添

20、弧称为最优解。333333221142例2：找出下列段道图的最优解33333322114233223最优解33321 需要顺便提到的是：既然可由一笔画画成的脉络，其奇点个数应不多于两个，那么，两笔划或多笔划能够画成的脉络，其奇点个数应有怎样的限制呢？ 一般地，我们有： 含有2n(n0)个奇点的脉络，需要n笔划画成。橡皮膜上的几何学橡皮膜上的几何学 在在哥尼斯堡七桥哥尼斯堡七桥问题中，大家已问题中，大家已经看到了一种只研究图形各部分位置的相经看到了一种只研究图形各部分位置的相对次序，而不考虑它们尺寸大小的新几何对次序，而不考虑它们尺寸大小的新几何学。莱布尼兹学。莱布尼兹(Leibniz，1646

21、1716)和欧和欧拉为这种拉为这种“位置几何学位置几何学”的发展奠定了基的发展奠定了基础。如今这一新的几何学，已经发展成一础。如今这一新的几何学，已经发展成一门重要的数学分支门重要的数学分支 在拓扑学中人们感兴趣的只是图形的位置而不是它的在拓扑学中人们感兴趣的只是图形的位置而不是它的大小。有人把拓扑学说成是橡皮膜上的几何学是很恰当的。大小。有人把拓扑学说成是橡皮膜上的几何学是很恰当的。因为橡皮膜上的图形，随着橡皮膜的拉动，其长度、曲直、因为橡皮膜上的图形，随着橡皮膜的拉动，其长度、曲直、面积等等都将发生变化。面积等等都将发生变化。请大家思考：“串”、“田”两字，在橡皮膜上可变为什么图形 拓扑学

22、是在拓扑学是在19世纪末兴起并在世纪末兴起并在20世纪蓬世纪蓬勃发展的数学分支，与近世代数、近代分析共勃发展的数学分支，与近世代数、近代分析共同成为数学的三大支柱。同成为数学的三大支柱。 拓扑学已在物理、化学、生物一些工程拓扑学已在物理、化学、生物一些工程技术中得到越来越广泛的应用。拓扑学主要研技术中得到越来越广泛的应用。拓扑学主要研究几何图形在一对一的双方连续变换下不同的究几何图形在一对一的双方连续变换下不同的性质，这种性质称为性质，这种性质称为“拓扑性质拓扑性质” 哈密顿图哈密顿图 起源于起源于1856年英年英Hamilton设计的名为周游设计的名为周游世界的游戏。在一个实心的正十二面体的

23、二十世界的游戏。在一个实心的正十二面体的二十个顶点上标以世界各地有名的二十座城市的名个顶点上标以世界各地有名的二十座城市的名字，要求游戏者沿十二面体的棱从一个城市出字，要求游戏者沿十二面体的棱从一个城市出发，经过每座城市恰好一次再回到出发点。发，经过每座城市恰好一次再回到出发点。将十二面体投影到平将十二面体投影到平面上：将十二面体的面上：将十二面体的顶点与棱分别对应图顶点与棱分别对应图的顶点和边，就得到的顶点和边，就得到一个正十二面体图。一个正十二面体图。则问题等价于在正十则问题等价于在正十二面体图中找一个圈，二面体图中找一个圈，包含图中一切顶点包含图中一切顶点Hamilton圈。圈。1201

24、918172 定义：定义： 图图G中的一圈，若它通过中的一圈，若它通过G中每个顶中每个顶点恰好一次，则该圈称为哈密尔顿圈，具点恰好一次，则该圈称为哈密尔顿圈，具有哈密尔顿圈的图称为哈密尔顿无向图。有哈密尔顿圈的图称为哈密尔顿无向图。 完全图必是哈密尔顿图。完全图必是哈密尔顿图。 从定义可知，一个图的从定义可知，一个图的Hamilton圈与圈与Euler环游是很相似的，差别在于环游是很相似的，差别在于Hamilton圈是环游圈是环游G的所有顶点圈的所有顶点圈（点不重，当然（点不重，当然边也不重），边也不重），而而Euler环游是环游环游是环游G的所的所有边的闭迹有边的闭迹（链，点可以重）。（链，

25、点可以重）。 对于一个图是否存在对于一个图是否存在Euler环游存在一环游存在一个非常简洁的判别法。但是到目前为止还没个非常简洁的判别法。但是到目前为止还没有找到有找到Hamilton图的充要条件。这是图论图的充要条件。这是图论尚未解决的主要问题之一。尚未解决的主要问题之一。图中 (1), (3),不是哈密尔顿图,(2) 为哈密尔顿图. 哈密尔顿图的判定哈密尔顿图的判定定理定理(必要条件必要条件1) 设无向图设无向图G=是哈密尔顿是哈密尔顿图图,V1是是V的任意的非空子集的任意的非空子集, k(G-V1)V1.其中其中, k(G-V1)为从为从G中删除中删除V1(删除删除V1中各顶点及中各顶点

26、及关联的边关联的边)后所得图的连通分支数后所得图的连通分支数.图图1图图2 图图3证明：假设证明：假设: C为为G中的一条哈密顿圈。可知中的一条哈密顿圈。可知 K (G-V1) K (C-V1) 当当V1中顶点在中顶点在C上均不相邻时上均不相邻时, K(C-V1)达到最大值达到最大值|V1|;图图2图图4当当V1中顶点在中顶点在C上彼此相邻的情况时上彼此相邻的情况时, 均有均有: K (C-V1) =1 |V1|。一般说来一般说来,V1中的顶点在中的顶点在C上既有相邻的上既有相邻的,又有不相又有不相邻的邻的,因而总有因而总有K(C-V1) V1.又因为又因为C是是G的生成子图的生成子图,故故

27、K(G-V1) K(C-V1) V1. 不是不是H-H-图。图。因为因为使得使得() 3 | |wG SS ) () () (),(),(,GpvdudGEuvGVvuUV说明:该定理只是一个必要条件,如下的皮特森图,尽管有k(G-V1)V1 但它不是哈密顿图. 1. Dirac(1952) 是简单图且 ，若 ，则 是H-图。 2)()(GpG ) ( ) ( ) ( ),(),(,Gpv du dGEuvGVv u2. Ore (1960)。 二、充分条件二、充分条件 Ore条件条件 是简单图且 ， 则 是H-图。 G()3p G ()3p G ) ( ) ( ) ( ),(),(,Gpv

28、du dGEuvGVv u在图中，任意两个结点的度数之和为在图中，任意两个结点的度数之和为4，结点，结点数为数为6，即有，即有4 6，但它仍然是，但它仍然是哈密尔顿图哈密尔顿图。1983年，范更华给出的一个充分条件 图 是一个2-连通图，对图 中的任意两个顶点 ，只要 就有则 是Hamilton图。GGvu和2),(vudG2)(),(maxpvdudGG例例1 假设有假设有8位来自不同国家的人参加某此国际会议的预备会位来自不同国家的人参加某此国际会议的预备会议。已知他们中任何两个无共同语言的人中的每一个议。已知他们中任何两个无共同语言的人中的每一个, 与其余有共与其余有共同语言的人数之和大于

29、或等于同语言的人数之和大于或等于8, 问能否将这问能否将这8个人排在圆桌旁个人排在圆桌旁, 使使任何人都能与两边的人交谈。任何人都能与两边的人交谈。解：解：设设8个人分别为个人分别为v1, v2, , v8, 以其为顶点作无向简单图以其为顶点作无向简单图G = , vi, vj V, i j, 若若vi与与vj有共同语言有共同语言, 作无向边作无向边(vi, vj), 由由此可得到边集合此可得到边集合E, 则则G为为8阶无向简单图。阶无向简单图。 vi V, d(vi)为与为与vi有共同语言的人数。有共同语言的人数。由已知条件可知由已知条件可知: vi, vj V且且i j, 均有均有: d(

30、vi)+d(vj) 8。由定理可知由定理可知: G中存在哈密顿圈。中存在哈密顿圈。哈密顿图的应用哈密顿图的应用例例2. 11个学生要共进晚餐个学生要共进晚餐,他们将坐成一个圆桌他们将坐成一个圆桌,计划要求计划要求每次晚餐上每次晚餐上,每个学生有完全不同的邻座每个学生有完全不同的邻座.这样能共进晚这样能共进晚餐几次餐几次. 分析分析:如何将该问题转化成图论中的相关问题如何将该问题转化成图论中的相关问题.实际实际上上,可以这样来构造一个图可以这样来构造一个图,即以每个学生看作图的顶点即以每个学生看作图的顶点,以学生的邻座关系作为图的以学生的邻座关系作为图的的边的边, 这样学生每次进餐的就坐方式就对

31、应一个哈密顿这样学生每次进餐的就坐方式就对应一个哈密顿圈圈.两次进餐中两次进餐中,每个学生有完全不同的邻座对应着两每个学生有完全不同的邻座对应着两个没有公共边的哈密顿圈个没有公共边的哈密顿圈.因为每个学生都可以与其因为每个学生都可以与其余学生邻座余学生邻座,故问题转化为在图故问题转化为在图K11中找出所有没有公中找出所有没有公共边的哈密顿圈的个数共边的哈密顿圈的个数. K11中共有中共有 条边条边,而而K11中每条哈密顿圈的长中每条哈密顿圈的长度为度为11,因此因此K11中最多有中最多有55/11=5条没有公共边的哈条没有公共边的哈密顿圈。密顿圈。211C= 55构造方法为构造方法为:设第一条

32、哈密顿圈为设第一条哈密顿圈为(1,2,3,11,1),将将1固固定在圆心定在圆心,其余固定在圆周上其余固定在圆周上,如图如图(1)所示所示,然后将图的顶然后将图的顶点旋转点旋转i 3600/10(i=1,2,3,4),从而就得到另外从而就得到另外4个哈密个哈密顿圈顿圈. 1 (3,2,4,6)5 7(5,3,2,4) (2,4,6,8 )3 9(7,5,3,2) (4,6,8,10)2 11(9,7,5,3) ( 6,8,10,11)4 10 (11,9,7,5) (8,10,11,9)6 8(10,11,9,7)图图1 1 连通图，若存在连通图，若存在 ，则则 是是H- -图当且仅当图当且仅

33、当 是是H- -图图。 GuvG 定理定理 定理定理4.3.4利用条件2证明中的2、3步骤即可返回 结束证明： 充分性显然 必要性：设C是 H-圈， 1.当uv不在C上时，成立； 2.当uv在C中时，用条件2可以证明G中含有一 条包含C-uv所有顶点的圈即可。uvG利用定理4.3.4， 依次连接度之和至少是 的两个不相邻点对()()C GG 的 闭 包)( GC证明：证明：（反证法） 1.设两个闭包 ，G到 添加的边为 添加的边是 2.令 为第一条不属于 的边。 令 ，在H中添加边 ， 3.可得 ， 因 是闭包得： 矛盾。21,GG1Gkeee,212Gleee ,21vven12GneeeG

34、H,211ne GpvdvdGG222G GpvdvdGG22返回 结束第三个条件与闭包有关，先来了解有关闭包的概念 。定理定理4.3.7 图G的闭包c(G)是惟一的。返回 结束根据 的构造及上面的定理4.3.4，易得以下结论： GC 定理定理4.3.5 图G是Hamilton图当且仅当 是Hamilton图。 GC 推论推论4.3.6 若图G的闭包 是完全图，则当 时， G是Hamilton图。 GC 3Gp例注： ()()2 . ,(),(), ()() ()CGCGxyVGx yEC Gd x d y pG 3. 由性质， 是H-图当且仅当 是H-图。 1 . () () )V GV C

35、 G还可以利用推论4.3.6来推导一个图是Hamilton图的几个顶点度表达的充分条件。例如，当 时， 显然是完全图，故当 时，G是Hamilton图。当G满足条件2时，也是完全图，故G是Hamilton图。返回 结束2)()(GpG GC 3Gp GC介绍Chvatl在1972年给出的充分条件定理定理4.3.84.3.8 的度序列为 。若 ，或有 ，或有 ，则 是H-图。 kdk返回 结束证明：证明：由推论4.3.6知，只要证明 的闭包是完全图。1. 假设 不是完全图，则可以取 使 最大。不妨设 则由 的假设， 。接下来证明对这个k，不满足定理的条件)(GC)(GCEuv)()()()(vd

36、udGCGC)()()()(vdudGCGC)(GC )()(udkGC2pG2. 记对于 ，我们有 中每个点在 的度不超过 中每个点在 的度不超过 且 )(,)(GCExvvGVxxS)(,)(GCExuuGVxxTTS和S)(GC)(GCkudGC)()(T1)()(kpvdGCkS kpuT3. 由于 是 的生成子图，因而在 中有个点的度不超过 ,以及至少有 个顶点的度 小于所以对 ,有 和 矛盾，定理得证。)(GCkp kp 2pkdkkpdkp kkkGG注意：定理4.3.8只是一个Hamilton图的充分条件而不是必 要条件。这个定理比条件1和条件2更强。由定理4.3.8有以下推论

37、：推论4.3.9 设图G的度序列为 若对 ，均有 。若p为奇数，更有则G是Hamilton图。3,2121pddddddpp211 ,pkkkdk121121pdp证明：1.若p为偶数，对 ，必有 故有定理的条件 ，由定理4.3.8知G是Hamilton图 2.若p为奇数，对 有 ， 而对 ，有 ， 按定理条件： 故由定理4.3.8知，G是Hamilton图。2pk 21pkkdk21pkkdk21pk21pkpkppddpkp12121返回 结束证明证明 取 则可以证明 的每个连通分支是完全图 ，且每个分支与 之间至少有两条边，同时由闭包定理，我们不妨假设 是完全图。由此可以构造出 的一个Hamilton圈。 2)(),(pudGVuuSGSG SSGG 设有P个城镇，已知每两个城镇之间的距离，一个售货员自某一城镇出发巡回售货，问这个售