第三章 哈密顿图.ppt

1、,邢台学院数学系,欢迎同学们！,第三章 欧拉图和哈密顿图,欧拉（L.Euler,1707.4.15- 1783.9.18）著名的数学家。生于瑞士的巴塞尔，卒于彼得堡。大部分时间在俄国和德国度过。他早年在数学天才贝努里赏识下开始学习数学, 17岁获得硕士学位，毕业后研究数学,是数学史上最高产的作家。在世发表论文700多篇,去世后还留下100多篇待发表。其论著几乎涉及所有数学分支。,欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领域，常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如、i、e、sin、cos、tg、x、f(x)等，都是他创立并推广的。欧拉还首

2、先完成了月球绕地球运动的精确理论，创立了分析力学、刚体力学等力学学科，深化了望远镜、显微镜的设计计算理论。,第一部分 欧拉图 1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”(下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。,欧拉圈、欧拉图 定义 图G中的一圈，若它通过G中的每一条边(或弧)恰好一次，则称该圈为欧拉圈，具有这种圈的图称为欧拉无向(或有向)图。,定理1 无向图G是欧拉图, 当且仅当G是连通图,

3、 且G中没有奇度顶点。 证：设G = 是含有m条边的n阶非平凡无向图, 其中: V = v1, v2, , vn 。 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的连通性和无奇度顶点可知: G只能是一个环, 因此, G为欧拉图。 (2) 设

4、m k(k 1)时, 结论成立要证明m = K+1时, 结论也成立。,由G的连通性和无奇度顶点可知: (G) 2。用扩大路径法可以证明G中存在长度大于或等于3的圈。 设C为G中一个圈, 删除C上的全部边, 得G的生成子图G。设G有s个连通分支G1, G2, , Gs, 每个连通分支至多有k条边, 且无奇度顶点, 并且设Gi与C的公共顶点为vji*(i = 1.s)。,由归纳假设可知: G1, G2, , Gs都是欧拉图, 因此, 都存在欧拉圈Ci(i = 1.s)。 现在将C还原(即将删除的边重新加上), 并从C上的某顶点vr开始进行遍历, 每遇到vji*, 就行遍Gi中的欧拉圈Ci(i=1.

5、s), 最后, 回到vr, 得圈C”: vr vj1* vj1* vj2* vj2* vjs* vjs* vr。 此圈C”经过G中每条边一次且仅一次。因此, C”是G中的欧拉圈(如右下图所示)。 故, G为欧拉图。,定理2 连通图G具有欧拉路而无欧拉圈,当且仅当G恰有两个奇数度顶点. 证:必要性:设连通图G从顶点a到顶点b有欧拉路C,但不是欧拉圈.在欧拉路C中,除第一边和最后一边外,每经过G中顶点xi(包括a和b),都为顶点xi贡献2度,而C的第一边为a贡献1度,C的最后一条边为b贡献1度.因此,a和b的度数均为奇数,其余结点度数均为偶数.,充分性:设连通图G恰有两个奇数度结点, 不妨设为a和

6、b,在图G中添加一条边e=a,b 得G,则G的每个结点的度数均为偶数,因 而G中存在欧拉圈,故G中必存在欧拉路.,什么叫一笔画？什么样的图可以一笔画出？,所谓图的一笔画，指的就是：从图的 一点出发，笔不离纸，遍历每条边恰 好一次，即每条边都只画一次，不准 重复.从上图中容易看出：能一笔 画出的图首先必须是连通图,欧拉定理：,凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。 其他情况的图，都不能一笔画出。,“一笔划”问题,？,这是一些平面图

7、形，请你思考图形能否一笔画出与什么有关？,例1 观察下面的图形，说明哪些图可以一笔画完，哪些能，为什么？对于可以一笔画的图形，指明画法,例2 下图是国际奥委会的会标，你能一笔把它画出来吗？,构造欧拉圈,思想：在画欧拉圈时，已经经过的边不能再用。因此，在构造欧拉圈过程中的任何时刻，假设将已经经过的边删除，剩下的边必须仍在同一连通分支当中。,设G为欧拉图, 通常情况下, G中存在若干条欧拉圈。下面介绍一种求欧拉圈的算法。 1Fleury算法 (1) 任取v0V(G), 令P0=v0 (2) 设Pi = v0e1v1e2eivi已经遍历, 按下面方法从E(G) - e1, e2, , ei 中选取e

8、i+1: ei+1与vi相关联 ei+1不应取Gi = G - e1, e2, , ei 中的桥, 除非无其它边可供行遍 (3) 重复步骤(2), 直到步骤(2)不能再进行为止。 可证明: 当算法停止时, 所得简单圈Pm = v0e1v1 e2 emvm(vm=v0)为G中一条欧拉圈。,关于一笔画问题的生活转化 1、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从A点出发，乙从B点出发，最后都回到邮局（C点）。如果要选择最短的线路，谁先回到邮局？,例2 下图是一个公园的平面图.要使游客走遍每条路而不重复，问出入口应设在哪里？,例(蚂蚁比赛问题) 甲、乙两只蚂蚁分别位于如下图中的结点A

9、，B处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？,例4 下图是某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个出口，问游人能否一次不重复地穿过所有的门，并且从入口进，从出口出？,设计展览会参观路线,A,B,C,J,E,F,I,K,H,G,D,L,N,M,O,H,G,O,F,E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,H,一人如果从门M进入，再从门K走出，他能否不重复地走过每一扇门？,例3 一张纸上画有如下图所示的图，你能否用剪刀一次

10、连续剪下图中的三个正方形和两个三角形？,下图画的两只动物世界的庞然大物，都可以用一笔画完成。它们的奇点个数分别为0和2。这两张图选自智力世界一刊，也算一种别有风趣的例子。,中国邮递员问题(Chinese Postman Problem, CPP)是由我国管梅谷教授于1962年首先提出并发表的 例如：观察下列段道图 问题：从邮局出发，走遍邮区的所有街道至少一次再回到邮局，按照什么样的路线投递邮件才能使总的路程最短？,中国邮递员问题,数学模型： 构造无向带权图G，E（G）中每个元素对应于辖区内的一条街道，V（G）中的元素对应于街道的交叉点，街道长度用相应边的权表示。 则问题的解对应于G中包含所有边

11、的权最小的圈，称为最优圈(注意：未必是简单圈)。 当G是欧拉图，则最优圈即欧拉圈。 若G不是欧拉图，则通过加边来消除G中的奇度顶点，要求使加边得到的欧拉图G中重复边的权和最小。,C是带正权无向连通图G中的最优圈当且仅当对应的欧拉图G*满足： (1) G的每条边在G*至多重复一次； (2) G的每个(初级)圈在G*重复边权的和不超过该圈权的一半。,算法过程 1用Dijstra算法求所有奇度顶点对之间的最短路径。(若G是欧拉图，直接用Fleury算法) 2以G中所有奇度顶点构造带权完全图G2k, 每边的权是两端点间最短路径长度。 3求G2k中的最小权完美匹配M。 4按照M中的各个路径添加重复边。

12、再用Fleury算法求欧拉圈。,欧拉圈 最理想的投递路线，就是该段道图是一条欧拉圈。图（2）的投递路线如下图（3）。 含有奇点的段道图不能一笔画出，有些道路需要重复走两次的都要添上一条弧。图（1）添弧后如图（4）。,最优投递路线 重复的路最短 添弧的总长度最短 添弧最短的条件 （1）没有重叠的添弧 （2）每一个圈上添弧的总长度不超过圈长的一半 最短的一组添弧称为最优解。,例2：找出下列段道图的最优解,先分奇偶点，奇点对对连 连线不重叠，重叠要改变 圈上连线长，不得过半圈,3,3,3,2,1,需要顺便提到的是：既然可由一笔画画成的脉络，其奇点个数应不多于两个，那么，两笔划或多笔划能够画成的脉络，

13、其奇点个数应有怎样的限制呢？ 一般地，我们有： 含有2n(n0)个奇点的脉络，需要n笔划画成。,橡皮膜上的几何学 在哥尼斯堡七桥问题中，大家已经看到了一种只研究图形各部分位置的相对次序，而不考虑它们尺寸大小的新几何学。莱布尼兹(Leibniz，16461716)和欧拉为这种“位置几何学”的发展奠定了基础。如今这一新的几何学，已经发展成一门重要的数学分支拓扑学,在拓扑学中人们感兴趣的只是图形的位置而不是它的大小。有人把拓扑学说成是橡皮膜上的几何学是很恰当的。因为橡皮膜上的图形，随着橡皮膜的拉动，其长度、曲直、面积等等都将发生变化。不过，在橡皮膜几何里也有一些图形的性质保持不变。例如点变化后仍然是

14、点；线变化后依旧为线；相交的图形绝不因橡皮的拉伸和弯曲而变得不相交!拓扑学正是研究诸如此类，使图形在橡皮膜上保持不变性质的几何学,请大家思考：“串”、“田”两字，在橡皮膜上可变为什么图形,拓扑学是在19世纪末兴起并在20世纪蓬勃发展的数学分支，与近世代数、近代分析共同成为数学的三大支柱。 拓扑学已在物理、化学、生物一些工程技术中得到越来越广泛的应用。拓扑学主要研究几何图形在一对一的双方连续变换下不同的性质，这种性质称为“拓扑性质”,哈密顿图 起源于1856年英Hamilton设计的名为周游世界的游戏。在一个实心的正十二面体的二十个顶点上标以世界各地有名的二十座城市的名字，要求游戏者沿十二面体的

15、棱从一个城市出发，经过每座城市恰好一次再回到出发点。,将十二面体投影到平面上：将十二面体的顶点与棱分别对应图的顶点和边，就得到一个正十二面体图。则问题等价于在正十二面体图中找一个圈，包含图中一切顶点Hamilton圈。,定义： 图G中的一圈，若它通过G中每个顶点恰好一次，则该圈称为哈密尔顿圈，具有哈密尔顿圈的图称为哈密尔顿无向图。 完全图必是哈密尔顿图。,从定义可知，一个图的Hamilton圈与Euler环游是很相似的，差别在于Hamilton圈是环游G的所有顶点圈（点不重，当然边也不重），而Euler环游是环游G的所有边的闭迹（链，点可以重）。 对于一个图是否存在Euler环游存在一个非常简

16、洁的判别法。但是到目前为止还没有找到Hamilton图的充要条件。这是图论尚未解决的主要问题之一。,图中 (1), (3),不是哈密尔顿图,(2) 为哈密尔顿图.,哈密尔顿图的判定 定理(必要条件1) 设无向图G=是哈密尔顿图,V1是V的任意的非空子集, k(G-V1)V1. 其中, k(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数.,证明：假设: C为G中的一条哈密顿圈。可知 K (G-V1) K (C-V1) 当V1中顶点在C上均不相邻时, K(C-V1)达到最大值|V1|;,当V1中顶点在C上彼此相邻的情况时, 均有: K (C-V1) =1 |V1|。,

17、一般说来,V1中的顶点在C上既有相邻的,又有不相邻的,因而总有K(C-V1) V1. 又因为C是G的生成子图,故 K(G-V1) K(C-V1) V1.,不是H-图。 因为 使得,说明:该定理只是一个必要条件,如下的皮特森图,尽 管有k(G-V1)V1 但它不是哈密顿图.,1. Dirac(1952),是简单图且 ，若 ，则 是H-图。,2. Ore (1960),。,二、充分条件,Ore条件 是简单图且 ， 则 是H-图。,在图中，任意两个结点的度数之和为4，结点数为6，即有46，但它仍然是哈密尔顿图。,1983年，范更华给出的一个充分条件 图 是一个2-连通图，对图 中的任 意两个顶点 ，

18、只要 就有 则 是Hamilton图。,例1 假设有8位来自不同国家的人参加某此国际会议的预备会议。已知他们中任何两个无共同语言的人中的每一个, 与其余有共同语言的人数之和大于或等于8, 问能否将这8个人排在圆桌旁, 使任何人都能与两边的人交谈。 解：设8个人分别为v1, v2, , v8, 以其为顶点作无向简单图G = , vi, vjV, i j, 若vi与vj有共同语言, 作无向边(vi, vj), 由此可得到边集合E, 则G为8阶无向简单图。 viV, d(vi)为与vi有共同语言的人数。 由已知条件可知: vi, vjV且i j, 均有: d(vi)+d(vj) 8。 由定理可知:

19、G中存在哈密顿圈。,哈密顿图的应用,例2. 11个学生要共进晚餐,他们将坐成一个圆桌,计划要求每次晚餐上,每个学生有完全不同的邻座.这样能共进晚餐几次. 分析:如何将该问题转化成图论中的相关问题.实际上,可以这样来构造一个图,即以每个学生看作图的顶点,以学生的邻座关系作为图的的边,这样学生每次进餐的就坐方式就对应一个哈密顿圈.两次进餐中,每个学生有完全不同的邻座对应着两个没有公共边的哈密顿圈.因为每个学生都可以与其余学生邻座,故问题转化为在图K11中找出所有没有公共边的哈密顿圈的个数. K11中共有 条边,而K11中每条哈密顿圈的长度为11,因此K11中最多有55/11=5条没有公共边的哈密顿

20、圈。,构造方法为:设第一条哈密顿圈为(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,连通图，若存在 ，则 是H-图当且仅当 是H-图。,定理,定理4.3.4,利用条件2证明中的2、3步骤即可,返回 结束,证明： 充分性显然 必

21、要性：设C是 H-圈， 1.当uv不在C上时，成立； 2.当uv在C中时，用条件2可以证明G中含有一 条包含C-uv所有顶点的圈即可。,证明：（反证法） 1.设两个闭包 ，G到 添加的边为 添加的边是 2.令 为第一条不属于 的边。 令 ，在H中添加边 ， 3.可得 ， 因 是闭包得： 矛盾。,返回 结束,第三个条件与闭包有关，先来了解有关闭包的概念 。,定理4.3.7 图G的闭包c(G)是惟一的。,返回 结束,根据 的构造及上面的定理4.3.4，易得以下结论：,定理4.3.5 图G是Hamilton图当且仅当 是Hamilton图。,推论4.3.6 若图G的闭包 是完全图，则当 时， G是H

22、amilton图。,例,还可以利用推论4.3.6来推导一个图是Hamilton图的几个顶点度表达的充分条件。例如，当 时， 显然是完全图，故当 时，G是Hamilton图。当G满足条件2时， 也是完全图，故G是Hamilton图。,4,5,4,5,4,6,3,6,返回 结束,介绍Chvatl在1972年给出的充分条件 定理4.3.8,的度序列为 。若 ，或有 ，或有 ，则 是H-图。,返回 结束,证明：由推论4.3.6知，只要证明 的闭包是完全图。 1. 假设 不是完全图，则可以取 使 最大。不妨设 则由 的假设， 。 接下来证明对这个k，不满足定理的条件,2. 记 对于 ，我们有 中每个点在

23、 的度不超过 中每个点在 的度不超过 且,3. 由于 是 的生成子图，因而在 中有个点的度不超过 ,以及至少有 个顶点的度 小于 所以对 ,有 和 矛盾，定理得证。,注意：定理4.3.8只是一个Hamilton图的充分条件而不是必 要条件。这个定理比条件1和条件2更强。,由定理4.3.8有以下推论：,推论4.3.9 设图G的度序列为 若对 ，均有 。若p为奇数，更有 则G是Hamilton图。,证明：1.若p为偶数，对 ，必有 故有定理的条件 ，由定理4.3.8知G是Hamilton图 2.若p为奇数，对 有 ， 而对 ，有 ， 按定理条件： 故由定理4.3.8知，G是Hamilton图。,返回 结束,证明 取 则可以证明 的每个连通分支是完全 图 ，且每个分支与 之间至少有两条边，同 时由闭包定理，我们不妨假设 是完全图。 由此可以构造出 的一个Hamilton圈。,设有P个城镇，已知每两个城镇之间的距离，一个售货员自某一城镇出发巡回售货，问这个售货员应如何选择路线，能使每个城镇经过一次且仅一次，最后返回到出发地，而使总的行程最短。这个问题称为旅行售货员问题。易看出，旅行售货员问题就是在一个赋权完全图中，找一个具有最小权的Hamilton圈。称这种圈为最优Hamilton圈。 这