第三章-哈密顿图优秀PPT.ppt

邢台学院数学系邢台学院数学系邢台学院数学系邢台学院数学系欢迎欢迎同学们！同学们！1第三章第三章 欧拉图和哈密顿图欧拉图和哈密顿图2欧拉（欧拉（L.Euler,1707.4.15-L.Euler,1707.4.15-1783.9.181783.9.18）著名的数学家。）著名的数学家。生于瑞士的巴塞尔，卒于彼得生于瑞士的巴塞尔，卒于彼得堡。大部分时间在俄国和德国堡。大部分时间在俄国和德国度过。他早年在数学天才贝努度过。他早年在数学天才贝努里赏识下开始学习数学里赏识下开始学习数学,17,17岁岁获得硕士学位，毕业后研究数获得硕士学位，毕业后研究数学学,是数学史上最高产的作家。是数学史上最高产的作家。在世发表论文在世发表论文700700多篇多篇,去世后去世后还留下还留下100100多篇待发表。其论多篇待发表。其论著几乎涉及所有数学分支。著几乎涉及所有数学分支。3欧拉在数学、物理、天文、建筑以至音乐、哲欧拉在数学、物理、天文、建筑以至音乐、哲学方面都取得了辉煌的成就。在数学的各个领学方面都取得了辉煌的成就。在数学的各个领域，常常见到以欧来命名的公式、定理、和重域，常常见到以欧来命名的公式、定理、和重要常数。课本上常见的如要常数。课本上常见的如、i、e、sin、cos、tg、x、f(x)等，都是他创立并推广的。欧等，都是他创立并推广的。欧拉还首先完成了月球绕地球运动的精确理论，拉还首先完成了月球绕地球运动的精确理论，创立了分析力学、刚体力学等力学学科，深化创立了分析力学、刚体力学等力学学科，深化了望远镜、显微镜的设计计算理论。了望远镜、显微镜的设计计算理论。4 第一部分第一部分 欧拉图欧拉图 1736年瑞士数学家欧拉发表了图论的第一篇年瑞士数学家欧拉发表了图论的第一篇著名论文著名论文“哥尼斯堡七桥问题哥尼斯堡七桥问题”(下称七桥问题下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生假日，有些城市居民进行环城周游，于是便产生了能否了能否“从某地出发，通过每桥恰好一次，在走从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处遍了七桥后又返回到原处”的问题。的问题。5678 欧拉圈、欧拉图欧拉圈、欧拉图定义定义 图图G中的一圈，若它通过中的一圈，若它通过G中的每一条中的每一条边边(或弧或弧)恰好一次，则称该圈为欧拉圈，具恰好一次，则称该圈为欧拉圈，具有这种圈的图称为欧拉无向有这种圈的图称为欧拉无向(或有向或有向)图。图。9定理定理1 无向图无向图G是欧拉图是欧拉图,当且仅当当且仅当G是连通图是连通图,且且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中无奇度顶点。中无奇度顶点。102).充分性充分性由由G为非平凡的连通图可知为非平凡的连通图可知:G中边数中边数m 1。对对m作归纳。作归纳。(1)m=1时时,由由G的连通性和无奇度顶点可的连通性和无奇度顶点可知知:G只能是一个环只能是一个环,因此因此,G为欧拉图。为欧拉图。(2)设设m k(k 1)时时,结论成立要证明结论成立要证明m=K+1时时,结论也成立。结论也成立。11 由由G的连通性和无奇度顶点可知的连通性和无奇度顶点可知:(G)2。用扩大路径法可以证明。用扩大路径法可以证明G中存在长度大于中存在长度大于或等于或等于3的圈。的圈。设设C为为G中一个圈中一个圈,删除删除C上的全部边上的全部边,得得G的生成子图的生成子图G。设。设G有有s个连通分支个连通分支G1,G2,Gs,每个连通分支至多有每个连通分支至多有k条边条边,且无且无奇度顶点奇度顶点,并且设并且设Gi与与C的公共顶点为的公共顶点为vji*(i=1.s)。12由归纳假设可知由归纳假设可知: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中每条边一次且仅一次。因此中每条边一次且仅一次。因此,C”是是G中的欧拉圈中的欧拉圈(如右下图所示如右下图所示)。故故,G为欧拉图。为欧拉图。13定理定理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 xi i贡献贡献2 2度度,而而C C的第一边为的第一边为a a贡献贡献1 1度度,C,C的最后一条的最后一条边为边为b b贡献贡献1 1度度.因此因此,a,a和和b b的度数均为奇数的度数均为奇数,其余其余结点度数均为偶数结点度数均为偶数.14充分性充分性:设连通图设连通图G恰有两个奇数度结点恰有两个奇数度结点,不妨设为不妨设为a和和b,在图在图G中添加一条边中添加一条边e=a,b得得G,则则G的每个结点的度数均为偶数的每个结点的度数均为偶数,因因而而G中存在欧拉圈中存在欧拉圈,故故G中必存在欧拉路中必存在欧拉路.151617凡是由偶点组成的连通图，一定可以一笔凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。能以这个点为终点画完此图。凡是只有两个奇点（其余均为偶点）的连凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。奇点为起点，另一个奇点为终点。其他情况的图，都不能一笔画出。其他情况的图，都不能一笔画出。18“一笔划一笔划”问题问题？19这是一些平面图形，请你思考图形能否一笔画出与什么有关？20例例1 1 观察下面的图形，说明哪些图可以一笔画完，哪些能，为什观察下面的图形，说明哪些图可以一笔画完，哪些能，为什么？对于可以一笔画的图形，指明画法么？对于可以一笔画的图形，指明画法 21例例2 下图是国际奥委会的会下图是国际奥委会的会标，你能一笔把它画出来标，你能一笔把它画出来吗？吗？22构造欧拉圈 思思想想：在在画画欧欧拉拉圈圈时时，已已经经经经过过的的边边不不能能再再用用。因因此此，在在构构造造欧欧拉拉圈圈过过程程中中的的任任何何时时刻刻，假假设设将将已已经经经经过过的的边边删删除除，剩剩下下的的边边必必须须仍仍在在同同一一连连通分支当中。通分支当中。23设设G为欧拉图为欧拉图,通常情况下通常情况下,G中存在若干条欧拉圈。中存在若干条欧拉圈。下面介绍一种求欧拉圈的算法。下面介绍一种求欧拉圈的算法。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中一条欧拉圈。中一条欧拉圈。2425关于一笔画问题的生活转化关于一笔画问题的生活转化1、甲乙两个邮递员去送信，两人以同样的速度走遍、甲乙两个邮递员去送信，两人以同样的速度走遍所有的街道，甲从所有的街道，甲从A点出发，乙从点出发，乙从B点出发，最后点出发，最后都回到邮局（都回到邮局（C点）。如果要选择最短的线路，谁点）。如果要选择最短的线路，谁先回到邮局？先回到邮局？DCEFB A26DABCEFGHIJK 例例2 下图是一个公园的平面图下图是一个公园的平面图.要使游客走遍要使游客走遍每条路而不重复，问出入口应设在哪里？每条路而不重复，问出入口应设在哪里？27甲甲A乙乙BC例例(蚂蚁比赛问题蚂蚁比赛问题)甲、乙两只蚂蚁分别位于如下图中的结点A，B处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？28例例4 下图是某展览厅的平面图，它由五个展室下图是某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个出口，问游人能否一厅还有一个进口和一个出口，问游人能否一次不重复地穿过所有的门，并且从入口进，次不重复地穿过所有的门，并且从入口进，从出口出？从出口出？29设计展览会参观路线设计展览会参观路线ABCJEFIKHGDLNMOABCIJDKLMNHOEGFH,G,O,F,E,N,M,O,L,K,I,L,M,J,N,D,C,J,B,I,A,K,H30MHIEFJKGDABC一人如果从门一人如果从门M进入进入，再从再从门门K走出走出，他能，他能否不重复地走否不重复地走过每一扇门？过每一扇门？31 例例3 3 一张纸上画有如下图所示的图，你能否用剪刀一一张纸上画有如下图所示的图，你能否用剪刀一次连续剪下图中的三个正方形和两个三角形？次连续剪下图中的三个正方形和两个三角形？HABCDEFGM32 下图画的两只动物世界的庞然大物，都下图画的两只动物世界的庞然大物，都可以用一笔画完成。它们的奇点个数分别为可以用一笔画完成。它们的奇点个数分别为0和和2。这两张图选自。这两张图选自智力世界智力世界一刊，也算一刊，也算一种别有风趣的例子。一种别有风趣的例子。33中国邮递员问题中国邮递员问题(Chinese Postman Problem,CPP)是由我是由我国管梅谷教授于国管梅谷教授于1962年首先提出并发表的年首先提出并发表的例如：观察下列段道图例如：观察下列段道图 问题：从邮局出发，走遍邮区的所有街道至少一次再回到邮问题：从邮局出发，走遍邮区的所有街道至少一次再回到邮局，按照什么样的路线投递邮件才能使总的路程最短？局，按照什么样的路线投递邮件才能使总的路程最短？中国邮递员问题中国邮递员问题图图2图图134 数学模型：数学模型：构造无向带权图构造无向带权图G，E（G）中每个元素对应）中每个元素对应于辖区内的一条街道，于辖区内的一条街道，V（G）中的元素对应于街）中的元素对应于街道的交叉点，街道长度用相应边的权表示。道的交叉点，街道长度用相应边的权表示。则问题的解对应于则问题的解对应于G中包含所有边的权最小中包含所有边的权最小的圈，称为最优圈的圈，称为最优圈(注意：未必是简单圈注意：未必是简单圈)。当当G是欧拉图，则最优圈即欧拉圈。是欧拉图，则最优圈即欧拉圈。若若G不是欧拉图，则通过加边来消除不是欧拉图，则通过加边来消除G中的奇中的奇度顶点，要求使加边得到的欧拉图度顶点，要求使加边得到的欧拉图G中重复边的中重复边的权和最小。权和最小。35C是带正权无向连通图是带正权无向连通图G中的最优圈当且仅当对应中的最优圈当且仅当对应的欧拉图的欧拉图G*满足：满足：(1)G的每条边在的每条边在G*至多重复一次；至多重复一次；(2)G的每个的每个(初级初级)圈在圈在G*重复边权的和不超过该圈重复边权的和不超过该圈权的一半。权的一半。36l算法过程算法过程1用用Dijstra算法求所有奇度顶点对之间的最短路径。算法求所有奇度顶点对之间的最短路径。(若若G是欧拉图，直接用是欧拉图，直接用Fleury算法算法)2以以G中所有奇度顶点构造带权完全图中所有奇度顶点构造带权完全图G2k,每边的每边的权是两端点间最短路径长度。权是两端点间最短路径长度。3求求G2k中的最小权完美匹配中的最小权完美匹配M。4按照按照M中的各个路径添加重复边。中的各个路径添加重复边。再用再用Fleury算算法求欧拉圈。法求欧拉圈。3738欧拉圈欧拉圈 最理想的投递路线，就是该段道图是一条欧拉圈。图（最理想的投递路线，就是该段道图是一条欧拉圈。图（2）的投递路线如下图（的投递路线如下图（3）。）。含有奇点的段道图不能一笔画出，有些道路需要重复走两次含有奇点的段道图不能一笔画出，有些道路需要重复走两次的都要添上一条弧。图（的都要添上一条弧。图（1）添弧后如图（）添弧后如图（4）。）。图图3图图439最优投递路线最优投递路线 重复的路最短重复的路最短 添弧的总长度最添弧的总长度最短短添弧最短的条件添弧最短的条件（1）没有重叠的添弧）没有重叠的添弧（2）每一个圈上添弧的总长度不超过圈长的一半）每一个圈上添弧的总长度不超过圈长的一半最短的一组添弧称为最优解。最短的一组添弧称为最优解。40333333221142例2：找出下列段道图的最优解4133333322114233223最优解 先分奇偶点，奇点对对连先分奇偶点，奇点对对连 连线不重叠，重叠要改变连线不重叠，重叠要改变 圈上连线长，不得过半圈圈上连线长，不得过半圈423332143 需要顺便提到的是：既然可由一笔画画成的脉络，其奇点个数应不多于两个，那么，两笔划或多笔划能够画成的脉络，其奇点个数应有怎样的限制呢？一般地，我们有：含有2n(n0)个奇点的脉络，需要n笔划画成。44橡皮膜上的几何学橡皮膜上的几何学 在在哥尼斯堡七桥哥尼斯堡七桥问题中，大家已问题中，大家已经看到了一种只研究图形各部分位置的相经看到了一种只研究图形各部分位置的相对次序，而不考虑它们尺寸大小的新几何对次序，而不考虑它们尺寸大小的新几何学。莱布尼兹学。莱布尼兹(Leibniz，16461716)和欧和欧拉为这种拉为这种“位置几何学位置几何学”的发展奠定了基的发展奠定了基础。如今这一新的几何学，已经发展成一础。如今这一新的几何学，已经发展成一门重要的数学分支门重要的数学分支拓扑学拓扑学45 在拓扑学中人们感兴趣的只是图形的位置而不是它的在拓扑学中人们感兴趣的只是图形的位置而不是它的大小。有人把拓扑学说成是橡皮膜上的几何学是很恰当的。大小。有人把拓扑学说成是橡皮膜上的几何学是很恰当的。因为橡皮膜上的图形，随着橡皮膜的拉动，其长度、曲直、因为橡皮膜上的图形，随着橡皮膜的拉动，其长度、曲直、面积等等都将发生变化。面积等等都将发生变化。不过，在橡皮膜几何里也有一些不过，在橡皮膜几何里也有一些不过，在橡皮膜几何里也有一些不过，在橡皮膜几何里也有一些图形的性质保持不变。例如点变化后仍然是点；线变化后图形的性质保持不变。例如点变化后仍然是点；线变化后图形的性质保持不变。例如点变化后仍然是点；线变化后图形的性质保持不变。例如点变化后仍然是点；线变化后依旧为线；相交的图形绝不因橡皮的拉伸和弯曲而变得不依旧为线；相交的图形绝不因橡皮的拉伸和弯曲而变得不依旧为线；相交的图形绝不因橡皮的拉伸和弯曲而变得不依旧为线；相交的图形绝不因橡皮的拉伸和弯曲而变得不相交相交相交相交!拓扑学正是研究诸如此类，使图形在橡皮膜上保持不拓扑学正是研究诸如此类，使图形在橡皮膜上保持不拓扑学正是研究诸如此类，使图形在橡皮膜上保持不拓扑学正是研究诸如此类，使图形在橡皮膜上保持不变性质的几何学变性质的几何学变性质的几何学变性质的几何学46请大家思考：“串”、“田”两字，在橡皮膜上可变为什么图形47 拓扑学是在拓扑学是在19世纪末兴起并在世纪末兴起并在20世纪蓬世纪蓬勃发展的数学分支，与近世代数、近代分析共勃发展的数学分支，与近世代数、近代分析共同成为数学的三大支柱。同成为数学的三大支柱。拓扑学已在物理、化学、生物一些工程技拓扑学已在物理、化学、生物一些工程技术中得到越来越广泛的应用。拓扑学主要研究术中得到越来越广泛的应用。拓扑学主要研究几何图形在一对一的双方连续变换下不同的性几何图形在一对一的双方连续变换下不同的性质，这种性质称为质，这种性质称为“拓扑性质拓扑性质”48 哈密顿图哈密顿图 起起源源于于1856年年英英Hamilton设设计计的的名名为为周周游游世世界界的的游游戏戏。在在一一个个实实心心的的正正十十二二面面体体的的二二十十个个顶顶点点上上标标以以世世界界各各地地有有名名的的二二十十座座城城市市的的名名字字，要要求求游游戏戏者者沿沿十十二二面面体体的的棱棱从从一一个个城城市市出出发，经过每座城市恰好一次再回到出发点。发，经过每座城市恰好一次再回到出发点。49将十二面体投影到平将十二面体投影到平面上：将十二面体的面上：将十二面体的顶点与棱分别对应图顶点与棱分别对应图的顶点和边，就得到的顶点和边，就得到一个正十二面体图。一个正十二面体图。则问题等价于在正十则问题等价于在正十二面体图中找一个圈，二面体图中找一个圈，包含图中一切顶点包含图中一切顶点Hamilton圈。圈。50120191817251 定义：定义：图图G中的一圈，若它通过中的一圈，若它通过G中每个顶中每个顶点恰好一次，则该圈称为哈密尔顿圈，具点恰好一次，则该圈称为哈密尔顿圈，具有哈密尔顿圈的图称为哈密尔顿无向图。有哈密尔顿圈的图称为哈密尔顿无向图。完全图必是哈密尔顿图。完全图必是哈密尔顿图。52 从定义可知，一个图的从定义可知，一个图的Hamilton圈与圈与Euler环游是很相似的，差别在于环游是很相似的，差别在于Hamilton圈是环游圈是环游G的所有顶点圈的所有顶点圈（点不重，当然（点不重，当然边也不重），边也不重），而而Euler环游是环游环游是环游G的所的所有边的闭迹有边的闭迹（链，点可以重）。（链，点可以重）。对于一个图是否存在对于一个图是否存在Euler环游存在一环游存在一个非常简洁的判别法。但是到目前为止还没个非常简洁的判别法。但是到目前为止还没有找到有找到Hamilton图的充要条件。这是图论图的充要条件。这是图论尚未解决的主要问题之一。尚未解决的主要问题之一。53图中(1),(3),不是哈密尔顿图,(2)为哈密尔顿图.54哈密尔顿图的判定哈密尔顿图的判定定理定理(必要条件必要条件1)设无向图设无向图G=是哈密尔顿是哈密尔顿图图,V1是是V的任意的非空子集的任意的非空子集,k(G-V1)V1.其中其中,k(G-V1)为从为从G中删除中删除V1(删除删除V1中各顶点及中各顶点及关联的边关联的边)后所得图的连通分支数后所得图的连通分支数.55图图1图图256 图图3证明：假设证明：假设:C为为G中的一条哈密顿圈。可知中的一条哈密顿圈。可知 K(G-V1)K(C-V1)当当V1中顶点在中顶点在C上均不相邻时上均不相邻时,K(C-V1)达到最大值达到最大值|V1|;图图257图图4当当V1中顶点在中顶点在C上彼此相邻的情况时上彼此相邻的情况时,均有均有:K(C-V1)=1|V1|。一般说来一般说来,V1中的顶点在中的顶点在C上既有相邻的上既有相邻的,又有不相又有不相邻的邻的,因而总有因而总有K(C-V1)V1.又因为又因为C是是G的生成子图的生成子图,故故 K(G-V1)K(C-V1)V1.58不是不是H-H-图。图。因为因为使得使得UV59说明:该定理只是一个必要条件,如下的皮特森图,尽管有k(G-V1)V1 但它不是哈密顿图.601.Dirac(1952)是简单图且 ，若 ，则 是H-图。2.Ore(1960)。二、充分条件二、充分条件 Ore条件条件 是简单图且 ，则 是H-图。61在在图图中中，任任意意两两个个结结点点的的度度数数之之和和为为4，结结点点数为数为6，即有，即有4 6，但它仍然是，但它仍然是哈密尔顿图哈密尔顿图。621983年，范更华给出的一个充分条件 图 是一个2-连通图，对图 中的任意两个顶点 ，只要 就有则 是Hamilton图。63例例1 假设有假设有8位来自不同国家的人参加某此国际会议的预备会位来自不同国家的人参加某此国际会议的预备会议。已知他们中任何两个无共同语言的人中的每一个议。已知他们中任何两个无共同语言的人中的每一个,与其余有共与其余有共同语言的人数之和大于或等于同语言的人数之和大于或等于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(vi)+d(vj)8。由定理可知由定理可知:G中存在哈密顿圈。中存在哈密顿圈。哈密顿图的应用哈密顿图的应用64例例2.11个学生要共进晚餐个学生要共进晚餐,他们将坐成一个圆桌他们将坐成一个圆桌,计划要求计划要求每次晚餐上每次晚餐上,每个学生有完全不同的邻座每个学生有完全不同的邻座.这样能共进晚餐这样能共进晚餐几次几次.分析分析:如何将该问题转化成图论中的相关问题如何将该问题转化成图论中的相关问题.实际上实际上,可以这样来构造一个图可以这样来构造一个图,即以每个学生看作图的顶点即以每个学生看作图的顶点,以学以学生的邻座关系作为图的生的邻座关系作为图的的边的边,65 这样学生每次进餐的就坐方式就对应一个哈密顿这样学生每次进餐的就坐方式就对应一个哈密顿圈圈.两次进餐中两次进餐中,每个学生有完全不同的邻座对应着两每个学生有完全不同的邻座对应着两个没有公共边的哈密顿圈个没有公共边的哈密顿圈.因为每个学生都可以与其余因为每个学生都可以与其余学生邻座学生邻座,故问题转化为在图故问题转化为在图K11中找出所有没有公共中找出所有没有公共边的哈密顿圈的个数边的哈密顿圈的个数.K11中共有中共有 条边条边,而而K11中每条哈密顿圈的长中每条哈密顿圈的长度为度为11,因此因此K11中最多有中最多有55/11=5条没有公共边的哈密条没有公共边的哈密顿圈。顿圈。66构造方法为构造方法为:设第一条哈密顿圈为设第一条哈密顿圈为(1,2,3,11,1),将将1固固定在圆心定在圆心,其余固定在圆周上其余固定在圆周上,如图如图(1)所示所示,然后将图的顶然后将图的顶点旋转点旋转i 3600/10(i=1,2,3,4),从而就得到另外从而就得到另外4个哈密个哈密顿圈顿圈.67 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 168 连通图，若存在连通图，若存在 ，则则 是是H-图当且仅当图当且仅当 是是H-图图。定理定理697071 定理定理4.3.4利用条件2证明中的2、3步骤即可返回 结束证明：充分性显然 必要性：设C是 H-圈，1.当uv不在C上时，成立；2.当uv在C中时，用条件2可以证明G中含有一 条包含C-uv所有顶点的圈即可。72利用定理4.3.4，依次连接度之和至少是 的两个不相邻点对证明：证明：（反证法）1.设两个闭包 ，G到 添加的边为 添加的边是 2.令 为第一条不属于 的边。令 ，在H中添加边 ，3.可得 ，因 是闭包得：矛盾。返回 结束第三个条件与闭包有关，先来了解有关闭包的概念。定理定理4.3.7 图G的闭包c(G)是惟一的。73返回 结束根据 的构造及上面的定理4.3.4，易得以下结论：定理定理4.3.5 图G是Hamilton图当且仅当 是Hamilton图。推论推论4.3.6 若图G的闭包 是完全图，则当 时，G是Hamilton图。74例注：3.由性质，是H-图当且仅当 是H-图。还可以利用推论4.3.6来推导一个图是Hamilton图的几个顶点度表达的充分条件。例如，当 时，显然是完全图，故当 时，G是Hamilton图。当G满足条件2时，也是完全图，故G是Hamilton图。返回 结束75介绍Chvatl在1972年给出的充分条件定理定理4.3.84.3.8 的度序列为 。若 ，或有 ，或有 ，则 是H-图。返回 结束76证明：证明：由推论4.3.6知，只要证明 的闭包是完全图。1.假设 不是完全图，则可以取 使 最大。不妨设 则由 的假设，。接下来证明对这个k，不满足定理的条件 772.记对于 ，我们有 中每个点在 的度不超过 中每个点在 的度不超过 且 783.由于 是 的生成子图，因而在 中有个点的度不超过 ,以及至少有 个顶点的度 小于所以对 ,有 和 矛盾，定理得证。79注意：定理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图。返回 结束80证明证明 取 则可以证明 的每个连通分支是完全图，且每个分支与 之间至少有两条边，同时由闭包定理，我们不妨假设 是完全图。由此可以构造出 的一个Hamilton圈。81 设有P个城镇，已知每两个城镇之间的距离，一个售货员自某一城镇出发巡回售货，问这个售货员应如何选择路线，能使每个城镇经过一次且仅一次，最后返回到出发地，而使总的行程最短。这个问题称为旅行售货员问题。易看出，旅行售货员问题就是在一个赋权完全图中，找一个具有最小权的Hamilton圈。称这种圈为最优Hamilton圈。这个问题的应用十分广泛，但是目前还没有一个求解最优Hamilton圈的有效算法。下面给出一个较好的近似算法：最邻近算法最邻近算法4 旅行售货员问题旅行售货员问题返回 结束82返回 结束 求近似最优Hamilton最邻近算法：设 是一个赋权完全图，规定：对 中任何三个顶点 ，满足（1）任选一个点 作起点，找一条与 关联其权最小的一条边 ，的另一个端点记为 ，得一条路 ；（2）设已选出路 ，在 中取一个与 最近的相邻顶点 ，得 ；（3）若 ，用 代 返回（2）。否则记最后所得的C就是G的一条近似最优的Hamilton圈。用最邻近法求得的Hamilton圈一般不是最优的。通过修改可得到更短的Hamilton圈。83返回 结束 修改方法：设 是G的一个Hamilton圈，若存在 ，并且 则Hamilton圈 (它是由C删去边 和添加 而得到的）的权和 因而Hamilton圈 将是C的一个改进。在接连进行上述的一系列修改后，最后得到的这个Hamilton图不能再用此方法改进了，这个Hamilton圈虽然未必是最优的，但是有理由认为它常常是比较好的。84 我们可以利用Kruskal算法给出最优Hamilton圈解的下界的一个估计式。设v是赋权完全图G的任意一个点，用Kruskal算法求出一个G-v的一个最优树T，设C是G的一个最优Hamilton圈，显然C-v是G-v的一个生成树，因此 设G中与v关联而权最小和权次小的两条边分别是e和f，则因此，将是G的最优Hamilton圈的一个下界估计式。由此可见结合上面两个方法所得到的Hamilton圈是一个很好的近似解。返回 结束85返回 结束本章基本要求：本章基本要求：1.1.熟悉熟悉EulerEuler图、图、EulerEuler迹的定义；迹的定义；2.2.掌握掌握EulerEuler图的判别；图的判别；3.3.了解了解HamiltonHamilton圈的定义，掌握圈的定义，掌握HamiltonHamilton图的必要性图的必要性 及充分性，了解图的闭包的概念。及充分性，了解图的闭包的概念。86878889909192939495969798