欧拉图与哈密顿图.ppt

第第1515章章 欧拉图与哈密顿图欧拉图与哈密顿图离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程数学家欧拉数学家欧拉         欧拉，瑞士数学家，欧拉是科学欧拉，瑞士数学家，欧拉是科学史上最多史上最多产的一位杰出的数学家，他从的一位杰出的数学家，他从19岁开始开始发表表论文，直到文，直到76岁，他一生，他一生共写下了共写下了886本本书籍和籍和论文，其中在世文，其中在世时发表了表了700多篇多篇论文彼得堡科学院文彼得堡科学院为了整理他的著作，整整用了了整理他的著作，整整用了47年在他双目失明后的他双目失明后的17年年间，也没有停止，也没有停止对数学的研究，口述了好几本数学的研究，口述了好几本书和和400余余篇的篇的论文       欧拉欧拉对物理力学、天文学、物理力学、天文学、弹道学、航海学、建筑学、音道学、航海学、建筑学、音乐都有研究！有都有研究！有许多公式、定理、解法、函数、方程、常数等多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的欧拉写的数学教材在当是以欧拉名字命名的欧拉写的数学教材在当时一直被当作一直被当作标准教程19世世纪伟大的数学家高斯曾大的数学家高斯曾说过“研究欧拉的著作永研究欧拉的著作永远是了解数学的好方法是了解数学的好方法”。

欧拉欧拉还是数学符号是数学符号发明者，他明者，他创设的的许多数学符号，例如多数学符号，例如π，，i，，e，，sin，，cos，，tg，，Σ，，f (x)等等，等等，至今沿用至今沿用 哈密顿哈密顿 1805 1805年年8 8月月4 4日生于爱尔兰都柏林；日生于爱尔兰都柏林；18651865年年9 9月月2 2日卒于都日卒于都柏林．力学、数学、光学．哈密顿的父亲阿其巴德柏林．力学、数学、光学．哈密顿的父亲阿其巴德(Archibald Rowan Hamilton)(Archibald Rowan Hamilton)为都柏林市的一个初级律师．为都柏林市的一个初级律师．哈密顿自幼聪明，被称为神童．他三岁能读英语，会算术；哈密顿自幼聪明，被称为神童．他三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语．九岁便熟悉了波斯语，阿拉伯语和印地语．1414岁时，因在都岁时，因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头．柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头． 哈密顿工作勤奋，思想活跃．发表的论文一般都很简洁，别人不易读懂，哈密顿工作勤奋，思想活跃．发表的论文一般都很简洁，别人不易读懂，但手稿却很详细，因而很多成果都由后人整理而得．仅在三一学院图书馆中但手稿却很详细，因而很多成果都由后人整理而得．仅在三一学院图书馆中的哈密顿手稿，就有的哈密顿手稿，就有250250本笔记及大量学术通信和未发表论文．爱尔兰国家图本笔记及大量学术通信和未发表论文．爱尔兰国家图书馆还有一部分手稿．书馆还有一部分手稿． 　　他的研究工作涉及不少领域，成果最大的是光学、力学和四元数．他研究的　　他的研究工作涉及不少领域，成果最大的是光学、力学和四元数．他研究的光学是几何光学，具有数学性质；力学则是列出动力学方程及求解；因此哈光学是几何光学，具有数学性质；力学则是列出动力学方程及求解；因此哈密顿主要是数学家．但在科学史中影响最大的却是他对力学的贡献．密顿主要是数学家．但在科学史中影响最大的却是他对力学的贡献．哈密顿哈密顿量量是现代物理最重要的量，当我们得到哈密顿量，就意味着得到了全部。

是现代物理最重要的量，当我们得到哈密顿量，就意味着得到了全部 匈牙利数学家厄多斯匈牙利数学家厄多斯保罗保罗‧ ‧厄多斯厄多斯(1913-1996)(1913-1996)是一位匈牙利的数学家是一位匈牙利的数学家其父母都是匈牙利的高中数学教师其父母都是匈牙利的高中数学教师19831983年年以色列以色列政府颁给十万美元政府颁给十万美元““沃尔夫奖金沃尔夫奖金””（（WolfPrizeWolfPrize）就是由他和华裔美籍的陈省身教授平分就是由他和华裔美籍的陈省身教授平分厄多斯是当代发表最多数学论文的数学家，也是全世界和各种厄多斯是当代发表最多数学论文的数学家，也是全世界和各种各样不同国籍的数学家合作发表论文最多的人他发表了近各样不同国籍的数学家合作发表论文最多的人他发表了近10001000多篇的论文，平均一年要写和回答多篇的论文，平均一年要写和回答15001500多封有关于数学多封有关于数学问题的信他可以和任何大学的数学家合作研究，他每到一问题的信他可以和任何大学的数学家合作研究，他每到一处演讲就能和该处的一两个数学家合作写论文，据说多数的处演讲就能和该处的一两个数学家合作写论文，据说多数的情形是人们把一些本身长期解决不了的问题和他讨论，他可情形是人们把一些本身长期解决不了的问题和他讨论，他可以很快就给出了问题的解决方法或答案，于是人们赶快把结以很快就给出了问题的解决方法或答案，于是人们赶快把结果写下来，然后发表的时候放上他的名字，厄多斯的新的一果写下来，然后发表的时候放上他的名字，厄多斯的新的一篇论文就这样诞生了。

篇论文就这样诞生了 本章内容本章内容15.1 15.1 欧拉图欧拉图15.2 15.2 哈密顿图哈密顿图15.3 15.3 带权图与货郎担问题带权图与货郎担问题基本要求基本要求作业作业15.1 15.1 欧拉图欧拉图q历史背景－－哥尼斯堡七桥问题历史背景－－哥尼斯堡七桥问题q欧拉图是一笔画出的边不重复的回路欧拉图是一笔画出的边不重复的回路欧拉图欧拉图定义定义15.115.1 通过图（无向图或有向图）中通过图（无向图或有向图）中所有边一次且仅一次所有边一次且仅一次行遍图中所有顶点的通路称为行遍图中所有顶点的通路称为欧拉通路欧拉通路，通过图中所有边一，通过图中所有边一次并且仅一次行遍所有顶点的次并且仅一次行遍所有顶点的回路回路称为称为欧拉回路欧拉回路具有欧拉具有欧拉回路的图称为回路的图称为欧拉图欧拉图，具有欧拉通路而无欧拉回路的图称为，具有欧拉通路而无欧拉回路的图称为半欧拉图半欧拉图 说明说明欧拉通路是图中经过所有边的简单的生成通路欧拉通路是图中经过所有边的简单的生成通路( (经过所经过所有顶点的通路称为生成通路有顶点的通路称为生成通路) )欧拉回路是经过所有边的简单的生成回路。

欧拉回路是经过所有边的简单的生成回路 举例举例欧拉图欧拉图半欧拉图半欧拉图无欧拉通路无欧拉通路欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路无向欧拉图的判定定理无向欧拉图的判定定理无向欧拉图的判定定理无向欧拉图的判定定理 定理定理15.115.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通图，且是连通图，且G中没有奇中没有奇度顶点证明证明 若若G是平凡图，结论显然成立是平凡图，结论显然成立下面设下面设G为非平凡图，设为非平凡图，设G是是m条边的条边的n n阶无向图，阶无向图，并设并设G的顶点集的顶点集V＝＝{ {v1 1, ,v2 2,…,,…,vn} }必要性必要性因为G为欧拉图，所以为欧拉图，所以G中存在欧拉回路，中存在欧拉回路，设设C为为G中任意一条欧拉回路，中任意一条欧拉回路， vi, ,vj∈∈V，，vi, ,vj都在都在C上，上，因而因而vi, ,vj连通，所以连通，所以G为连通图为连通图又又 vi∈∈V，，vi在在C上每出现一次获得上每出现一次获得2 2度，度，若出现若出现k次就获得次就获得2 2k度，即度，即d( (vi) )＝＝2 2k，，所以所以G中无奇度顶点。

中无奇度顶点定理定理15.115.1的证明的证明充分性充分性由于G为非平凡的连通图可知，为非平凡的连通图可知，G中边数中边数m≥1≥1对对m作归纳法作归纳法 (1)(1)m＝＝1 1时，由时，由G的连通性及无奇度顶点可知，的连通性及无奇度顶点可知，G只能是一个环，因而只能是一个环，因而G G为欧拉图为欧拉图 (2)(2)设设m≤≤k( (k≥1)≥1)时结论成立，要证明时结论成立，要证明m＝＝k+1+1时，结论也成立时，结论也成立由由G的连通性及无奇度顶点可知，的连通性及无奇度顶点可知，δ(δ(G)≥2)≥2无论无论G是否为简单图，都可以用扩大路径法证明是否为简单图，都可以用扩大路径法证明G中必含圈中必含圈定理定理15.115.1的证明的证明设设C为为G中一个圈，删除中一个圈，删除C上的全部边，得上的全部边，得G的生成子图的生成子图G  ，，设设G  有有s个连通分支个连通分支G  1 1, ,G  2 2,…,,…,G  s，，每个连通分支至多有每个连通分支至多有k条边，且无奇度顶点，条边，且无奇度顶点，并且设并且设G  i与与C的公共顶点为的公共顶点为v* *ji，，i＝＝1,2,…,1,2,…,s，，由归纳假设可知，由归纳假设可知，G  1 1, ,G  2 2,…,,…,G  s都是欧拉图，都是欧拉图，因而都存在欧拉回路因而都存在欧拉回路C  i，，i＝＝1,2,…,1,2,…,s。

最后将最后将C还原（还原（即将删除的边重新加上即将删除的边重新加上），），并从并从C上的某顶点上的某顶点vr开始行遍，每遇到开始行遍，每遇到v* *ji，，就行遍就行遍G  i中的欧拉中的欧拉回路回路C  i，，i＝＝1,2,…,1,2,…,s，，最后回到最后回到vr，，得回路得回路vr……v* *j1 1……v* *j1 1……v* *j2 2……v* *j2 2……v* *js……v* *js……vr，，此回路经过此回路经过G中每条边一次且仅一次并行遍中每条边一次且仅一次并行遍G中所有顶点，中所有顶点，因而它是因而它是G中的欧拉回路（中的欧拉回路（演示这条欧拉回路演示这条欧拉回路），），故故G为欧拉图为欧拉图定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通的，且是连通的，且G中恰有两中恰有两个奇度顶点个奇度顶点证明证明 必要性必要性设G是是m条边的条边的n阶无向图，因为阶无向图，因为G为半欧拉图，为半欧拉图，因而因而G中存在欧拉通路中存在欧拉通路( (但不存在欧拉回路但不存在欧拉回路) )，，设设ГГ＝＝vi0 0ej1 1vi1 1……vim-1-1ejmvim为为G中一条欧拉通路，中一条欧拉通路，vi0 0≠≠vim。

 v∈∈V( (G) )，，若若v不在不在ГГ的端点出现，显然的端点出现，显然d( (v) )为偶数，为偶数，若若v在端点出现过，则在端点出现过，则d( (v) )为奇数，为奇数，因为因为ГГ只有两个端点且不同，因而只有两个端点且不同，因而G中只有两个奇数顶点中只有两个奇数顶点另外，另外，G的连通性是显然的的连通性是显然的半欧拉图的判定定理半欧拉图的判定定理半欧拉图的判定定理半欧拉图的判定定理定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通的，且是连通的，且G中恰有两中恰有两个奇度顶点个奇度顶点证明证明 充分性充分性设G的两个奇度顶点分别为的两个奇度顶点分别为u0 0和和v0 0，，对对G加新边（加新边（u0 0, ,v0 0），），得得G  ＝＝G∪(∪(u0 0, ,v0 0) )，，则则G  是连通且无奇度顶点的图，是连通且无奇度顶点的图，由定理由定理15.115.1可知，可知，G  为欧拉图，为欧拉图，因而存在欧拉回路因而存在欧拉回路C  ，，而而C＝＝C  -(-(u0 0, ,v0 0) )为为G中一条欧拉通路，中一条欧拉通路，所以所以G为半欧拉图。

为半欧拉图 半欧拉图的判定定理半欧拉图的判定定理半欧拉图的判定定理半欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理定理定理15.315.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶点的是强连通的且每个顶点的入度都等于出度入度都等于出度定理定理15.415.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中中恰有两个奇度顶点，其中一个的入度比出度大恰有两个奇度顶点，其中一个的入度比出度大1 1，另一个的出，另一个的出度比入度大度比入度大1 1，而其余顶点的入度都等于出度而其余顶点的入度都等于出度 (举例举例) )定理定理15.515.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干个边是连通的且为若干个边不重的圈的并不重的圈的并例例15.1 15.1 例例15.115.1 设设G是非平凡的且非环的欧拉图，证明：是非平凡的且非环的欧拉图，证明：(1)(1)λ(λ(G)≥2)≥22)(2)对于对于G中任意两个不同顶点中任意两个不同顶点u, ,v，，都存在简单回路都存在简单回路C含含u和和v。

证明证明 (1) (1)由定理由定理15.515.5可知，可知， e∈∈E( (G) )，，存在圈存在圈C，，e在在C中，中，因而因而p( (G- -e) )＝＝p( (G) )，，故故e不是桥由由e的任意性的任意性λ(λ(G)≥2)≥2，，即即G是是2 2边边- -连通图2)(2) u, ,v∈∈V( (G) )，，u≠≠v，，由由G的连通性可知，的连通性可知，u, ,v之间必存在路径之间必存在路径ГГ1 1，，设设G  ＝＝G- -E(Г(Г1 1) )，，则在则在G  中中u与与v还必连通，还必连通，否则，否则，u与与v必处于必处于G  的不同的连通分支中，的不同的连通分支中，这说明在这说明在ГГ1 1上存在上存在G中的桥，这与中的桥，这与(1)(1)矛盾于是在于是在G  中存在中存在u到到v的路径的路径ГГ2 2，，显然显然ГГ1 1与与ГГ2 2边不重，边不重，这说明这说明u, ,v处于处于ГГ1 1∪Г∪Г2 2形成的简单回路上形成的简单回路上求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法Fleury算法算法，，能不走桥就不走桥能不走桥就不走桥 (1) (1) 任取任取v0 0∈∈V( (G) )，，令令P0 0＝＝v0 0。

2) (2) 设设Pi＝＝v0 0e1 1v1 1e2 2……eivi已经行遍，按下面方法来从已经行遍，按下面方法来从 E( (G)-{)-{e1 1, ,e2 2,…,,…,ei} }中选取中选取ei+1+1：： (a) (a) ei+1+1与与vi相关联；相关联； ( (b) b) 除非无别的边可供行遍，否则除非无别的边可供行遍，否则ei+1+1不应该为不应该为 Gi＝＝G-{-{e1 1, ,e2 2,…,,…,ei} }中的桥3)(3)当当(2)(2)不能再进行时，算法停止不能再进行时，算法停止 说明说明可以证明，当算法停止时所得简单回路可以证明，当算法停止时所得简单回路Pm＝＝v0 0e1 1v1 1e2 2……emvm( (vm＝＝v0 0) )为为G中一条欧拉回路中一条欧拉回路FleuryFleury算法示例算法示例例例15.215.2下图是给定的欧拉图下图是给定的欧拉图G某人用某人用Fleury算法求算法求G中的欧拉回路时，中的欧拉回路时，走了简单回路走了简单回路v2 2e2 2v3 3e3 3v4 4e1414v9 9e1010v2 2e1 1v1 1e8 8v8 8e9 9v2 2之后之后( (观看他的错误观看他的错误走法走法) )，无法行遍了，试分析在哪步他犯了错误，无法行遍了，试分析在哪步他犯了错误? ? 解答解答 此人行遍此人行遍v8 8时犯了能不走桥就不走桥时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。

的错误，因而他没行遍出欧拉回路当他走到当他走到v8 8时，时，G-{-{e2 2, ,e3 3, ,e1414, ,e1010, ,e1 1, ,e8 8} }为下图所示为下图所示此时此时e9 9为该图中的桥，而为该图中的桥，而e7 7, ,e1111均不是桥，均不是桥，他不应该走他不应该走e9 9，，而应该走而应该走e7 7或或e1111，，他没他没有走，所以犯了错误注意，此人在行有走，所以犯了错误注意，此人在行遍中，在遍中，在v3 3遇到过桥遇到过桥e3 3，，v1 1处遇到过桥处遇到过桥e8 8，，但当时除桥外他无别的边可走，所以但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的当时均走了桥，这是不会犯错误的15.2 15.2 哈密顿图哈密顿图q历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图哈密顿图哈密顿图 定义定义15.215.2 经过图（有向图或无向图）中经过图（有向图或无向图）中所有顶点一次且仅一所有顶点一次且仅一次的通路次的通路称为称为哈密顿通路哈密顿通路经过图中经过图中所有顶点一次且仅一次所有顶点一次且仅一次的回路的回路称为称为哈密顿回路哈密顿回路。

具有哈密顿回路的图称为具有哈密顿回路的图称为哈密顿图哈密顿图，，具有哈密顿通路但不具有哈密顿回路的图称为具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图半哈密顿图平凡图是哈密顿图平凡图是哈密顿图说明说明哈密顿通路是图中生成的初级通路，哈密顿通路是图中生成的初级通路，哈密顿回路是生成的初级回路哈密顿回路是生成的初级回路判断一个图是否为哈密顿图，就是判断能否将图中所有顶点判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路都放置在一个初级回路( (圈圈) )上，但这不是一件易事上，但这不是一件易事与判断一个图是否为欧拉图不一样，到目前为止，人们还没与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件有找到哈密顿图简单的充分必要条件例题例题(1)(2)(1)(2)是哈密顿图是哈密顿图3)(3)是半哈密顿图是半哈密顿图4)(4)既不是哈密顿图，也不是半哈密顿图既不是哈密顿图，也不是半哈密顿图定理定理15.6 15.6 定理定理15.615.6 设无向图设无向图G＝＝< >是哈密顿图，对于任意是哈密顿图，对于任意V1 1 V，，且且V1 1≠≠，，均有均有p( (G- -V1 1)≤|)≤|V1 1| | 其中，其中，p( (G- -V1 1) )为为G- -V1 1的连通分支数。

的连通分支数 证明证明 设设C为为G中任意一条哈密顿回路，中任意一条哈密顿回路，易知，当易知，当V1 1中顶点在中顶点在C上均不相邻时，上均不相邻时，p( (C- -V1 1) )达到最大值达到最大值| |V1 1| |，，而当而当V1 1中顶点在中顶点在C上有彼此相邻的情况时，上有彼此相邻的情况时，均有均有p( (C- -V1 1) )＜＜| |V1 1| |，，所以有所以有 p( (C- -V1 1)≤|)≤|V1 1| |而而C是是G的生成子图，所以，有的生成子图，所以，有p( (G- -V1 1)≤)≤p( (C- -V1 1)≤|)≤|V1 1| |说明说明本定理的条件是哈密顿图的必要条件，但不是充分条件本定理的条件是哈密顿图的必要条件，但不是充分条件可以验证彼得松图满足定理中的条件，但不是哈密顿图可以验证彼得松图满足定理中的条件，但不是哈密顿图若一个图不满足定理中的条件，它一定不是哈密顿图若一个图不满足定理中的条件，它一定不是哈密顿图推论推论 推论推论 设无向图设无向图G＝＝< >是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 1 V且且V1 1≠≠，，均有均有 p( (G- -V1 1)≤|)≤|V1 1|+1 |+1 证明证明 设设P是是G中起于中起于u终于终于v的哈密顿通路，的哈密顿通路，令令G  ＝＝G∪(∪(u, ,v)()(在在G的顶点的顶点u, ,v之间加新边之间加新边) )，，易知易知G  为哈密顿图，为哈密顿图，由定理由定理15.615.6可知，可知，p( (G  - -V1 1)≤|)≤|V1 1| |。

因此，因此，p( (G- -V1 1) ) ＝＝ p( (G  - -V1 1-(-(u, ,v)))) ≤ ≤ p( (G  - -V1 1)+1)+1 ≤ | ≤ |V1 1|+1 |+1 例例15.315.3例例15.315.3 在下图中给出的三个图都是二部图它们中的哪些是在下图中给出的三个图都是二部图它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？哈密顿图？哪些是半哈密顿图？为什么？易知互补顶点子集易知互补顶点子集V1 1＝＝{ {a, ,f} }V2 2＝＝{ {b, ,c, ,d, ,e} }设此二部图为设此二部图为G1 1，，则则G1 1＝＝< >p( (G1 1- -V1 1) )＝＝4>|4>|V1 1| |＝＝2 2，，由定理由定理15.615.6及其推论可知，及其推论可知，G1 1不是哈密不是哈密顿图，也不是半哈密顿图顿图，也不是半哈密顿图 例例15.315.3设图为设图为G2 2，，则则G2 2＝＝< >，，其中其中V1 1＝＝{ {a, ,g, ,h, ,i, ,c} }，，V2 2＝＝{ {b, ,e, ,f, ,j, ,k, ,d} }，，易知，易知，p( (G2 2- -V1 1) )＝＝| |V2 2| |＝＝6>|6>|V1 1| |＝＝5 5，，由定理由定理15.615.6可知，可知，G2 2不是哈密顿图，不是哈密顿图，但但G2 2是半哈密顿图。

是半哈密顿图baegjckhfid为为G2 2中一条哈密顿通路中一条哈密顿通路设图为设图为G3 3G3 3＝＝< >，，其中其中V1 1＝＝{ {a, ,c, ,g, ,h, ,e} }，，V2 2＝＝{ {b, ,d, ,i, ,j, ,f} }，，G3 3中存在哈密顿回路中存在哈密顿回路如如 abcdgihjefa，，所以所以G3 3是哈密顿图是哈密顿图 例例15.315.3的说明的说明q哈密顿通路是经过图中所有顶点的一条初级通路哈密顿通路是经过图中所有顶点的一条初级通路q哈密顿回路是经过图中所有顶点的初级回路哈密顿回路是经过图中所有顶点的初级回路 q对于二部图还能得出下面结论：对于二部图还能得出下面结论： 一般情况下，设二部图一般情况下，设二部图G＝＝< >，，| |V1 1|≤||≤|V2 2| |，，且且| |V1 1|≥2|≥2，，| |V2 2|≥2|≥2，，由定理由定理15.615.6及其推论可以得出下面结论：及其推论可以得出下面结论：(1) (1) 若若G是哈密顿图，则是哈密顿图，则| |V1 1| |＝＝| |V2 2| |。

2) (2) 若若G是半哈密顿图，则是半哈密顿图，则| |V2 2| |＝＝| |V1 1|+1|+13) (3) 若若| |V2 2|≥||≥|V1 1|+2|+2，，则则G G不是哈密顿图，也不是半哈密顿图不是哈密顿图，也不是半哈密顿图 例例15.415.4 设设G是是n阶无向连通图证明：阶无向连通图证明：若若G中有割点或桥，则中有割点或桥，则G不是不是哈密顿图哈密顿图证明证明 可用定理可用定理15.615.6证明定理定理15.715.7定理定理15.715.7 设设G是是n阶无向简单图，若对于阶无向简单图，若对于G中任意不相邻的顶中任意不相邻的顶点点vi, ,vj，，均有均有d( (vi)+)+d( (vj)≥)≥n-1-1(15.1)(15.1)则则G中存在哈密顿通路中存在哈密顿通路 证明证明 首先证明首先证明G是连通图是连通图否则否则G至少有两个连通分支，至少有两个连通分支，设设G1 1, ,G2 2是阶数为是阶数为n1 1, ,n2 2的两个连通分支，的两个连通分支，设设v1 1∈∈V( (G1 1) )，，v2 2∈∈V( (G2 2) )，，因为因为G是简单图，所以是简单图，所以dG( (v1 1)+)+dG( (v2 2) )＝＝dG1 1( (v1 1)+)+dG2 2( (v2 2)≤)≤n1 1-1+-1+n2 2-1≤-1≤n-2-2　　这与这与(15.1)(15.1)矛盾，所以矛盾，所以G必为连通图。

必为连通图定理定理15.715.7下面证下面证G中存在哈密顿通路中存在哈密顿通路设设Г＝＝v1 1v2 2……vl为为G中用中用““扩大路径法扩大路径法””得到的得到的““极大路径极大路径””，，即即Г的始点的始点v1 1与终点与终点vl不与不与Г外的顶点相邻显然有外的顶点相邻显然有l≤≤n (1)(1)若若l＝＝n，，则则Г为为G中哈密顿通路中哈密顿通路2)(2)若若l＜＜n，，这说明这说明Г不是哈密顿通路，不是哈密顿通路，即即G中还存在着中还存在着Г外的顶点外的顶点但可以证明但可以证明G中存在经过中存在经过Г上所有顶点的圈上所有顶点的圈 (a)a) 若若v1 1与与vl相邻，即相邻，即( (v1 1, ,vl)∈)∈E( (G) )，，则则Г∪(∪(v1 1, ,vl) )为满足要求的圈为满足要求的圈 定理定理15.715.7( (b)b)若若v1 1与与vl不相邻，设不相邻，设v1 1与与Г上的上的vi1 1＝＝v2 2, ,vi2 2,…,,…,vik相邻相邻( (k≥2)≥2)( (否则否则 d( (v1 1)+)+d( (vl)≤1+)≤1+l-2=-2=l-1<-1

见下图所示于是，回路于是，回路C＝＝v1 1v2 2……vir -1-1vlvlr -1-1……vi……virv1 1过过Г上的所有顶点上的所有顶点定理定理15.715.7( (c)c)下面证明存在比下面证明存在比Г更长的路径更长的路径因为因为l<

为哈密顿图 证明证明 由定理由定理15.715.7可知，可知，G中存在哈密顿通路，中存在哈密顿通路，设设Г＝＝v1 1v2 2……vn为为G中一条哈密顿通路，中一条哈密顿通路，若若v1 1与与vn相邻，设边相邻，设边e＝＝( (v1 1, ,vn) )，，则则Г∪{∪{e} }为为G中哈密顿回路中哈密顿回路若若v1 1与与vn不相邻，应用不相邻，应用(15.2)(15.2)，同定理，同定理15.715.7证明中的证明中的(2)(2)类似，可类似，可证明存在过证明存在过Г上各顶点的圈，上各顶点的圈，此圈即为此圈即为G中的哈密顿回路中的哈密顿回路定理定理15.815.8定理定理15.815.8 设设u, ,v为为n阶无向图阶无向图G中两个不相邻的顶点，且中两个不相邻的顶点，且d( (u)+)+d( (v)≥)≥n，，则则G为哈密顿图当且仅当为哈密顿图当且仅当G∪(∪(u, ,v) )为哈密顿图为哈密顿图( (( (u, ,v) )是加的新边是加的新边) ) 证明证明( (略略) ) 例例15.515.5例例15.515.5 在在某某次次国国际际会会议议的的预预备备会会议议中中，，共共有有8 8人人参参加加，，他他们们来来自自不不同同的的国国家家。

已已知知他他们们中中任任何何两两个个无无共共同同语语言言的的人人中中的的每每一一个个，，与与其其余余有有共共同同语语言言的的人人数数之之和和大大于于或或等等于于8 8，，问问能能否否将将这这8 8个个人人排排在在圆桌旁，使其任何人都能与两边的人交谈圆桌旁，使其任何人都能与两边的人交谈 解答解答 设设8 8个人分别为个人分别为v1 1, ,v2 2,…,,…,v8 8，，作无向简单图作无向简单图G＝＝< >，，其中其中V＝＝{ {v1 1, ,v2 2,…,,…,v8 8} }，， vi, ,vj∈∈V，，且且i≠≠j，，若若vi与与vj有共同语言，就在有共同语言，就在vi, ,vj之间连无向边之间连无向边( (vi, ,vj) )，，由此组成边集合由此组成边集合E，，则则G为为8 8阶无向简单图，阶无向简单图， vi∈∈V，，d( (vi) )为与为与vi有共同语言的人数有共同语言的人数由已知条件可知，由已知条件可知， vi, ,vj∈∈V且且i≠≠j，，均有均有d( (vi)+)+d( (vj)≥8)≥8由定理由定理15.715.7的推论可知，的推论可知，G中存在哈密顿回路，中存在哈密顿回路，设设C＝＝vi1 1vi2 2……vi8 8为为G中一条哈密顿回路，中一条哈密顿回路，按这条回路的顺序安排座次即可。

按这条回路的顺序安排座次即可哈密顿图是能将图中所有顶哈密顿图是能将图中所有顶点都能安排在某个初级回路点都能安排在某个初级回路上的图 定理定理15.915.9定理定理15.915.9 若若D为为n( (n≥2)≥2)阶竞赛图，则阶竞赛图，则D中具有哈密顿通路中具有哈密顿通路 证明证明 对对n作归纳法作归纳法n＝＝2 2时，时，D的基图为的基图为K2 2，，结论成立结论成立设设n＝＝k时结论成立现在设时结论成立现在设n＝＝k+1+1设设V( (D) )＝＝{ {v1 1, ,v2 2,…,,…,vk, ,vk+1+1} }令令D1 1＝＝D- -vk+1+1，，易知易知D1 1为为k阶竞赛图，阶竞赛图，由归纳假设可知，由归纳假设可知，D1 1存在哈密顿通路，存在哈密顿通路，设设Г1 1＝＝v  1 1v  2 2……v  k为其中一条为其中一条定理定理15.915.9下面证明下面证明vk+1+1可扩到可扩到Г1 1中去若存在若存在v  r(1≤(1≤r≤≤k) )，，有有< ∈>∈E( (D) )，，i＝＝1,2,…,1,2,…,r -1-1，，而而< ∈>∈E( (D) )，，见左图所示，见左图所示，则则Г＝＝v  1 1v  2 2……v  r-1-1vk+1+1v  r……v  k为为D中哈密顿通路。

中哈密顿通路否则否则 i∈{1,2,…,∈{1,2,…,k} }，，均有均有< ∈>∈E( (D) )，，见右图所示，见右图所示，则则Г＝＝Г  ∪<∪ >为为D中哈密顿通路中哈密顿通路例例15.615.6下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？ (1)(1)存在哈密顿回路，所以存在哈密顿回路，所以(1)(1)为哈密顿图为哈密顿图2)(2)取取V1 1＝＝{ {a, ,b, ,c, ,d, ,e} }，，从图中删除从图中删除V1 1得得7 7个连通分支，个连通分支， 由定理由定理15.615.6和推论可知，不是哈密顿图，也不是半哈密顿图和推论可知，不是哈密顿图，也不是半哈密顿图3)(3)取取V1 1＝＝{ {b, ,e, ,h} }，，从图中删除从图中删除V1 1得得4 4个连通分支，由定理个连通分支，由定理15.615.6可可知，它不是哈密顿图但存在哈密顿通路，所以是半哈密顿图知，它不是哈密顿图但存在哈密顿通路，所以是半哈密顿图 基本要求基本要求q深刻理解欧拉图与半欧拉图的定义及判别定理。

深刻理解欧拉图与半欧拉图的定义及判别定理q会用会用Fleury算法求出欧拉图中的欧拉回路算法求出欧拉图中的欧拉回路q深刻理解哈密顿图及半哈密顿图的定义深刻理解哈密顿图及半哈密顿图的定义q会用破坏哈密顿图应满足的某些必要条件的方法判断某些会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图图不是哈密顿图q会用满足哈密顿图的充分条件的方法判断某些图是哈密顿会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图q严格地分清哈密顿图必要条件和充分条件，千万不能将必严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要要条件当充分条件，同样地，也不能将充分条件当成必要条件作业作业习题十五习题十五2 2、、1111、、1414、、1515、、2020例例15.415.4例例15.415.4 设设G是是n阶无向连通图证明：若阶无向连通图证明：若G中有割点或桥，则中有割点或桥，则G不不是哈密顿图是哈密顿图证明证明(1)(1)证明证明若若G中有割点，则中有割点，则G不是哈密顿图不是哈密顿图设设v为连通图为连通图G中一个割点，则中一个割点，则V  ＝＝{ {v} }为为G中的点割集，而中的点割集，而p( (G- -V  )≥2)≥2＞＞1 1＝＝| |V  | |由定理由定理15.615.6可知可知G不是哈密顿图。

不是哈密顿图2)(2)证明证明若若G中有桥，则中有桥，则G不是哈密顿图不是哈密顿图设设G中有桥，中有桥，e＝＝( (u, ,v) )为其中的一个桥为其中的一个桥若若u, ,v都是悬挂边，则都是悬挂边，则G为为K2 2，，K2 2不是哈密顿图不是哈密顿图若若u, ,v中至少有一个，比如中至少有一个，比如u，，d( (u)≥2)≥2，，由于由于e与与u关联，关联，e为桥，为桥，所以所以G- -u至少产生两个连通分支，于是至少产生两个连通分支，于是u为为G中割点由由(1)(1)的讨论可知，的讨论可知，G不是哈密顿图不是哈密顿图。