欧拉图与哈密顿课件

1、第15章 欧拉图与哈密顿图 离离 散散 数数 学学 欧拉图与哈密顿课件 本章内容本章内容 15.1 15.1 欧拉图欧拉图 15.2 15.2 哈密顿图哈密顿图 15.3 15.3 带权图与货郎担问题带权图与货郎担问题 欧拉图与哈密顿课件 15.1 15.1 欧拉图欧拉图 q 历史背景哥尼斯堡七桥问题历史背景哥尼斯堡七桥问题 q 欧拉图是一笔画出的边不重复的回路欧拉图是一笔画出的边不重复的回路。 欧拉图与哈密顿课件 欧拉图欧拉图 定义定义15.115.1 通过图（无向图或有向图）中通过图（无向图或有向图）中所有边一次且仅一次所有边一次且仅一次 行遍图中行遍图中所有顶点所有顶点的通路称为的通路称

2、为欧拉通路欧拉通路，通过图中所有边，通过图中所有边 一次并且仅一次行遍所有顶点的一次并且仅一次行遍所有顶点的回路回路称为称为欧拉回路欧拉回路。具有。具有 欧拉回路的图称为欧拉回路的图称为欧拉图欧拉图，具有欧拉通路而无欧拉回路的，具有欧拉通路而无欧拉回路的 图称为图称为半欧拉图半欧拉图。 说明说明欧拉通路是图中经过所有边的简单的生成通路欧拉通路是图中经过所有边的简单的生成通路( (经过所经过所 有顶点的通路称为生成通路有顶点的通路称为生成通路) )。 欧拉回路是经过所有边的简单的生成回路。欧拉回路是经过所有边的简单的生成回路。 规定：平凡图是欧拉图规定：平凡图是欧拉图 欧拉图与哈密顿课件 举例举

3、例 欧拉图欧拉图半欧拉图半欧拉图无欧拉通路无欧拉通路 欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路 欧拉图与哈密顿课件 无向欧拉图的判定定理无向欧拉图的判定定理 定理定理15.115.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通图，且是连通图，且G中没有奇中没有奇 度顶点。度顶点。 证明证明 若若G是平凡图，结论显然成立。是平凡图，结论显然成立。 下面设下面设G为非平凡图，设为非平凡图，设G是是m条边的条边的n n阶无向图，阶无向图， 并设并设G的顶点集的顶点集V v1 1, ,v2 2,vn 。 必要性必要性。因为。因为G为欧拉图，所以为欧拉图，所以G中存在欧拉回路，中

4、存在欧拉回路， 设设C为为G中任意一条欧拉回路，中任意一条欧拉回路， vi, ,vjV，vi, ,vj都在都在C上，上， 因而因而vi, ,vj连通，所以连通，所以G为连通图。为连通图。 又又 viV，vi在在C上每出现一次获得上每出现一次获得2 2度，度， 若出现若出现k次就获得次就获得2 2k度，即度，即d( (vi) )2 2k， 所以所以G中无奇度顶点。中无奇度顶点。 欧拉图与哈密顿课件 定理定理15.115.1的证明的证明 充分性充分性。由于。由于G为非平凡的连通图可知，为非平凡的连通图可知，G中边数中边数m11。 对对m作归纳法。作归纳法。 (1)(1)m1 1时，由时，由G的连通

5、性及无奇度顶点可知，的连通性及无奇度顶点可知， G只能是一个环，因而只能是一个环，因而G G为欧拉图。为欧拉图。 (2)(2)设设mk( (k1)1)时结论成立，要证明时结论成立，要证明mk+1+1时，结论也成立。时，结论也成立。 由由G的连通性及无奇度顶点可知，的连通性及无奇度顶点可知，(G)2)2。 无论无论G是否为简单图，都可以用是否为简单图，都可以用扩大路径法扩大路径法证明证明G中必含圈。中必含圈。 欧拉图与哈密顿课件 定理定理15.115.1的证明的证明 设设C为为G中一个圈，删除中一个圈，删除C上的全部边，得上的全部边，得G的生成子图的生成子图G ， 设设G 有有s个连通分支个连通

6、分支G 1 1, ,G 2 2,G s， 每个连通分支至多有每个连通分支至多有k条边，且无奇度顶点，条边，且无奇度顶点， 并且设并且设G i与与C的公共顶点为的公共顶点为v* *ji，i1,2,1,2,s， 由归纳假设可知，由归纳假设可知，G 1 1, ,G 2 2,G s都是欧拉图，都是欧拉图， 因而都存在欧拉回路因而都存在欧拉回路C i，i1,2,1,2,s。 最后将最后将C还原（还原（即将删除的边重新加上即将删除的边重新加上），）， 并从并从C上的某顶点上的某顶点vr开始行遍，每遇到开始行遍，每遇到v* *ji，就行遍就行遍G i中的欧拉中的欧拉 回路回路C i，i1,2,1,2,s，最

7、后回到最后回到vr， 得回路得回路vrv* *j1 1v* *j1 1v* *j2 2v* *j2 2v* *jsv* *jsvr， 此回路经过此回路经过G中每条边一次且仅一次并行遍中每条边一次且仅一次并行遍G中所有顶点，中所有顶点， 因而它是因而它是G中的欧拉回路，中的欧拉回路， 故故G为欧拉图。为欧拉图。 欧拉图与哈密顿课件 欧拉图的判定定理欧拉图的判定定理 定理定理15.515.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干个边是连通的且为若干个边 不重的圈的并。不重的圈的并。 欧拉图与哈密顿课件 定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧

8、拉图当且仅当G是连通的，且是连通的，且G中恰有两中恰有两 个奇度顶点。个奇度顶点。 证明证明 必要性必要性。设。设G是是m条边的条边的n阶无向图，因为阶无向图，因为G为半欧拉图，为半欧拉图， 因而因而G中存在欧拉通路中存在欧拉通路( (但不存在欧拉回路但不存在欧拉回路) )， 设设v i0 0 e j1 1 v i1 1 v im-1 -1ejmvim为 为G中一条欧拉通路，中一条欧拉通路，v i0 0 vim。 vV( (G) )，若若v不在不在的端点出现，显然的端点出现，显然d( (v) )为偶数，为偶数， 若若v在端点出现过，则在端点出现过，则d( (v) )为奇数，为奇数， 因为因为只

9、有两个端点且不同，因而只有两个端点且不同，因而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 是连通且无奇度顶点的图，是连通且无奇度顶点的图， 由

10、定理由定理15.115.1可知，可知，G 为欧拉图，为欧拉图， 因而存在欧拉回路因而存在欧拉回路C ，而而CC -(-(u0 0, ,v0 0) )为为G中一条欧拉通路，中一条欧拉通路， 所以所以G为半欧拉图。为半欧拉图。 半欧拉图的判定定理半欧拉图的判定定理 欧拉图与哈密顿课件 有向欧拉图的判定定理有向欧拉图的判定定理 定理定理15.315.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶点的是强连通的且每个顶点的 入度都等于出度。入度都等于出度。 定理定理15.415.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中中 恰有

11、两个奇度顶点，其中一个的入度比出度大恰有两个奇度顶点，其中一个的入度比出度大1 1，另一个的出，另一个的出 度比入度大度比入度大1 1，而其余顶点的入度都等于出度。，而其余顶点的入度都等于出度。 欧拉图与哈密顿课件 例例15.1 15.1 例例15.115.1 设设G是非平凡的且非环的欧拉图，证明：是非平凡的且非环的欧拉图，证明： (1)(1)(G)2)2。 (2)(2)对于对于G中任意两个不同顶点中任意两个不同顶点u, ,v，都存在简单回路都存在简单回路C含含u和和v。 证明证明 (1) (1)由定理由定理15.515.5可知，可知， eE( (G) )，存在圈存在圈C，e在在C中，中， 因

12、而因而p( (G- -e) )p( (G) )，故故e不是桥。不是桥。 由由e的任意性的任意性(G)2)2，即即G是是2 2边边- -连通图。连通图。 (2)(2) u, ,vV( (G) )，uv，由由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与与

13、2 2边不重，边不重， 这说明这说明u, ,v处于处于1 12 2形成的简单回路上。形成的简单回路上。 欧拉图与哈密顿课件 求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法 Fleury算法算法，能不走桥就不走桥能不走桥就不走桥 (1) (1) 任取任取v0 0V( (G) )，令令P0 0v0 0。 (2) (2) 设设Piv0 0e1 1v1 1e2 2eivi已经行遍，按下面方法来从已经行遍，按下面方法来从 E( (G)-)-e1 1, ,e2 2,ei 中选取中选取ei+1 +1： ： (a) (a) ei+1 +1与 与vi相关联；相关联； ( (b) b) 除非无别的边可供行遍，否

14、则除非无别的边可供行遍，否则ei+1 +1不应该为 不应该为 GiG-e1 1, ,e2 2,ei 中的桥。中的桥。 (3)(3)当当(2)(2)不能再进行时，算法停止。不能再进行时，算法停止。 说明说明可以证明，当算法停止时所得简单回路可以证明，当算法停止时所得简单回路 Pmv0 0e1 1v1 1e2 2emvm( (vmv0 0) ) 为为G中一条欧拉回路。中一条欧拉回路。 欧拉图与哈密顿课件 FleuryFleury算法示例算法示例 欧拉图与哈密顿课件 例例15.215.2 下图是给定的欧拉图下图是给定的欧拉图G。某人用某人用Fleury算法求算法求G中的欧拉回路时中的欧拉回路时 ，走

15、了简单回路，走了简单回路v2 2e2 2v3 3e3 3v4 4e14 14v9 9e1010v2 2e1 1v1 1e8 8v8 8e9 9v2 2之后 之后( (观看他的观看他的 错误走法错误走法) )，无法行遍了，试分析在哪步他犯了错误，无法行遍了，试分析在哪步他犯了错误? ? 解答解答 此人行遍此人行遍v8 8时犯了能不走桥就不走桥时犯了能不走桥就不走桥 的错误，因而他没行遍出欧拉回路。的错误，因而他没行遍出欧拉回路。 当他走到当他走到v8 8时，时，G-e2 2, ,e3 3, ,e14 14, ,e1010, ,e1 1, ,e8 8 为下图所示。为下图所示。 此时此时e9 9为该

16、图中的桥，而为该图中的桥，而e7 7, ,e11 11均不是桥， 均不是桥， 他不应该走他不应该走e9 9，而应该走而应该走e7 7或或e11 11， ，他没他没 有走，所以犯了错误。注意，此人在行有走，所以犯了错误。注意，此人在行 遍中，在遍中，在v3 3遇到过桥遇到过桥e3 3，v1 1处遇到过桥处遇到过桥 e8 8，但当时除桥外他无别的边可走，所但当时除桥外他无别的边可走，所 以当时均走了桥，这是不会犯错误的。以当时均走了桥，这是不会犯错误的。 欧拉图与哈密顿课件 15.2 15.2 哈密顿图哈密顿图 q 历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图 欧拉

17、图与哈密顿课件 哈密顿图哈密顿图 定义定义15.215.2 经过图（有向图或无向图）中经过图（有向图或无向图）中所有顶点一次且仅一所有顶点一次且仅一 次的通路次的通路称为称为哈密顿通路哈密顿通路。经过图中。经过图中所有顶点一次且仅一所有顶点一次且仅一 次的回路次的回路称为称为哈密顿回路哈密顿回路。具有哈密顿回路的图称为。具有哈密顿回路的图称为哈密哈密 顿图顿图，具有哈密顿通路但不具有哈密顿回路的图称为，具有哈密顿通路但不具有哈密顿回路的图称为半哈半哈 密顿图密顿图。平凡图是哈密顿图。平凡图是哈密顿图。 说明说明哈密顿通路是图中生成的初级通路，哈密顿通路是图中生成的初级通路， 哈密顿回路是生成的

18、初级回路。哈密顿回路是生成的初级回路。 判断一个图是否为哈密顿图，就是判断能否将图中所有顶判断一个图是否为哈密顿图，就是判断能否将图中所有顶 点都放置在一个初级回路点都放置在一个初级回路( (圈圈) )上，但这不是一件易事。上，但这不是一件易事。 与判断一个图是否为欧拉图不一样，到目前为止，人们还与判断一个图是否为欧拉图不一样，到目前为止，人们还 没有找到哈密顿图简单的充分必要条件。没有找到哈密顿图简单的充分必要条件。 欧拉图与哈密顿课件 例题例题 (1)(2)(1)(2)是哈密顿图。是哈密顿图。 (3)(3)是半哈密顿图。是半哈密顿图。 (4)(4)既不是哈密顿图，也不是半哈密顿图。既不是哈

19、密顿图，也不是半哈密顿图。 欧拉图与哈密顿课件 定理定理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上有彼此相

20、邻的情况时，上有彼此相邻的情况时， 均有均有p( (C- -V1 1) )| |V1 1| |，所以有所以有 p( (C- -V1 1)|)|V1 1| |。 而而C是是G的生成子图，所以，有的生成子图，所以，有p( (G- -V1 1)p( (C- -V1 1)|)|V1 1| |。 说明说明本定理的条件是哈密顿图的必要条件，但不是充分条件。本定理的条件是哈密顿图的必要条件，但不是充分条件。 可以验证彼得松图满足定理中的条件，但不是哈密顿图。可以验证彼得松图满足定理中的条件，但不是哈密顿图。 若一个图不满足定理中的条件，它一定不是哈密顿图。若一个图不满足定理中的条件，它一定不是哈密顿图。 欧

21、拉图与哈密顿课件 推论推论 推论推论 设无向图设无向图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 -

22、 -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不是哈密不是哈密 顿图，也不是半哈

23、密顿图。顿图，也不是半哈密顿图。 欧拉图与哈密顿课件 例例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 3。G3 3 ，其中其中 V1 1 a, ,c, ,g, ,

24、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

25、2|2|2，由定理由定理15.615.6及其推论可以得出下面结论：及其推论可以得出下面结论： (1) (1) 若若G是哈密顿图，则是哈密顿图，则| |V1 1| | |V2 2| |。 (2) (2) 若若G是半哈密顿图，则是半哈密顿图，则| |V2 2| | |V1 1|+1|+1。 (3) (3) 若若| |V2 2|V1 1|+2|+2，则则G G不是哈密顿图，也不是半哈密顿图。不是哈密顿图，也不是半哈密顿图。 欧拉图与哈密顿课件 例例15.415.4 例例15.415.4 设设G是是n阶无向连通图。证明：若阶无向连通图。证明：若G中有割点或桥，则中有割点或桥，则G不不 是哈密顿图。是哈

26、密顿图。 证明证明(1)(1)证明证明若若G中有割点，则中有割点，则G不是哈密顿图。不是哈密顿图。 设设v为连通图为连通图G中一个割点，则中一个割点，则V v 为为G中的点割集，而中的点割集，而 p( (G- -V )2)21 1| |V | | 由定理由定理15.615.6可知可知G不是哈密顿图。不是哈密顿图。 (2)(2)证明证明若若G中有桥，则中有桥，则G不是哈密顿图。不是哈密顿图。 设设G中有桥，中有桥，e( (u, ,v) )为其中的一个桥。为其中的一个桥。 若若u, ,v都是悬挂点，则都是悬挂点，则G为为K2 2，K2 2不是哈密顿图。不是哈密顿图。 若若u, ,v中至少有一个，比

27、如中至少有一个，比如u，d( (u)2)2，由于由于e与与u关联，关联，e为桥为桥 ，所以，所以G- -u至少产生两个连通分支，于是至少产生两个连通分支，于是u为为G中割点。中割点。 由由(1)(1)的讨论可知，的讨论可知，G不是哈密顿图。不是哈密顿图。 欧拉图与哈密顿课件 定理定理15.715.7 定理定理15.715.7 设设G是是n阶无向简单图，若对于阶无向简单图，若对于G中任意不相邻的顶中任意不相邻的顶 点点vi, ,vj，均有均有 d( (vi)+)+d( (vj)n-1 -1 (15.1)(15.1) 则则G中存在哈密顿通路。中存在哈密顿通路。 证明证明 首先证明首先证明G是连通图

28、。是连通图。 否则否则G至少有两个连通分支，至少有两个连通分支， 设设G1 1, ,G2 2是阶数为是阶数为n1 1, ,n2 2的两个连通分支，的两个连通分支， 设设v1 1V( (G1 1) )，v2 2V( (G2 2) )，因为因为G是简单图，所以是简单图，所以 dG( (v1 1)+)+dG( (v2 2) )dG1 1( (v1 1)+)+dG2 2( (v2 2)n1 1-1+-1+n2 2-1-1n-2-2 这与这与(15.1)(15.1)矛盾，所以矛盾，所以G必为连通图。必为连通图。 欧拉图与哈密顿课件 定理定理15.715.7 下面证下面证G中存在哈密顿通路。中存在哈密顿通

29、路。 设设v1 1v2 2vl为为G中用中用“扩大路径法扩大路径法”得到的得到的“极大路径极大路径”， 即即的始点的始点v1 1与终点与终点vl不与不与外的顶点相邻。显然有外的顶点相邻。显然有ln。 (1)(1)若若ln，则则为为G中哈密顿通路。中哈密顿通路。 (2)(2)若若ln，这说明这说明不是哈密顿通路，不是哈密顿通路， 即即G中还存在着中还存在着外的顶点。外的顶点。 但可以证明但可以证明G中存在经过中存在经过上所有顶点的圈上所有顶点的圈。 ( (a)a) 若若v1 1与与vl相邻，即相邻，即( (v1 1, ,vl)E( (G) )， 则则(v1 1, ,vl) )为满足要求的圈。为满

30、足要求的圈。 欧拉图与哈密顿课件 定理定理15.715.7 ( (b)b)若若v1 1与与vl不相邻，设不相邻，设v1 1与与上的上的vi1 1v2 2, ,vi2 2,vik相邻相邻( (k2)2) ( (否则否则 d( (v1 1)+)+d( (vl)1+)1+l-2=-2=l-1-1n-1-1，这与这与(15.1)(15.1)矛盾矛盾) ) 此时，此时，vl至少与至少与vi2 2,vik相邻的顶点相邻的顶点vi2-1 2-1, ,vik-1 -1之一相邻 之一相邻 ( (否则否则 d( (v1 1)+)+d( (vl)k+ +l-2-(-2-(k-1)-1)l-1-1n-1-1) ) 设

31、设vl与与vir -1 -1相邻（ 相邻（22rk），），见下图所示。见下图所示。 于是，回路于是，回路 Cv1 1v2 2vir -1 -1vlvlr -1-1 vivirv1 1 过过上的所有顶点。上的所有顶点。 欧拉图与哈密顿课件 定理定理15.715.7 ( (c)c)下面证明存在比下面证明存在比更长的路径。更长的路径。 因为因为l n，所以所以C外还有顶点，由外还有顶点，由G的连通性可知，的连通性可知， 存在存在v l+1 +1 V( (G)-)-V( (C) )与与C上某顶点上某顶点vt相邻，见下图所示。相邻，见下图所示。 删除边删除边( (vt-1 -1, ,vt) )得路径 得

32、路径 vt-1 -1 v1 1virvlvir-1 -1 vtvl+1 +1比 比长度大长度大1 1， 对对 上的顶点重新排序，使其成为上的顶点重新排序，使其成为 v1 1v2 2vlv l+1 1 ， 对对 重复重复( (a)a)(c)(c)，在有限步内一定得到在有限步内一定得到G的哈密顿通路。的哈密顿通路。 欧拉图与哈密顿课件 定理定理15.715.7的推论的推论 推论推论 设设G为为n( (n3)3)阶无向简单图，若对于阶无向简单图，若对于G中任意两个不相邻的中任意两个不相邻的 顶点顶点vi, ,vj，均有均有 d( (vi)+)+d( (vj)n (15.2)(15.2) 则则G中存在

33、哈密顿回路，从而中存在哈密顿回路，从而G为哈密顿图。为哈密顿图。 证明证明 由定理由定理15.715.7可知，可知，G中存在哈密顿通路，中存在哈密顿通路， 设设v1 1v2 2vn为为G中一条哈密顿通路，中一条哈密顿通路， 若若v1 1与与vn相邻，设边相邻，设边e( (v1 1, ,vn) )，则则e 为为G中哈密顿回路。中哈密顿回路。 若若v1 1与与vn不相邻，应用不相邻，应用(15.2)(15.2)，同定理，同定理15.715.7证明中的证明中的(2)(2)类似，可类似，可 证明存在过证明存在过上各顶点的圈，上各顶点的圈， 此圈即为此圈即为G中的哈密顿回路。中的哈密顿回路。 欧拉图与哈

34、密顿课件 定理定理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人参加，他们来自不人参加，他们来自不 同的国家。已知他们中任何两个无共同语言的人中的每一个，与同的国家。已知他们中任何

35、两个无共同语言的人中的每一个，与 其余有共同语言的人数之和大于或等于其余有共同语言的人数之和大于或等于8 8，问能否将这，问能否将这8 8个人排在个人排在 圆桌旁，使其任何人都能与两边的人交谈。圆桌旁，使其任何人都能与两边的人交谈。 解答解答 设设8 8个人分别为个人分别为v1 1, ,v2 2,v8 8，作无向简单图作无向简单图G ， 其中其中V v1 1, ,v2 2,v8 8 ， vi, ,vjV，且且ij， 若若vi与与vj有共同语言，就在有共同语言，就在vi, ,vj之间连无向边之间连无向边( (vi, ,vj) )， 由此组成边集合由此组成边集合E，则则G为为8 8阶无向简单图，阶

36、无向简单图， viV，d( (vi) )为与为与vi有共同语言的人数。有共同语言的人数。 由已知条件可知，由已知条件可知， vi, ,vjV且且ij，均有均有d( (vi)+)+d( (vj)8)8。 由定理由定理15.715.7的推论可知，的推论可知，G中存在哈密顿回路，中存在哈密顿回路， 设设Cvi1 1vi2 2vi8 8为为G中一条哈密顿回路，中一条哈密顿回路， 按这条回路的顺序安排座次即可。按这条回路的顺序安排座次即可。 欧拉图与哈密顿课件 定理定理15.915.9 定理定理15.915.9 若若D为为n( (n2)2)阶竞赛图，则阶竞赛图，则D中具有哈密顿通路。中具有哈密顿通路。

37、证明证明 对对n作归纳法。作归纳法。 n2 2时，时，D的基图为的基图为K2 2，结论成立。结论成立。 设设nk时结论成立。现在设时结论成立。现在设nk+1+1。 设设V( (D) ) v1 1, ,v2 2,vk, ,v k+1 +1 。 。 令令D1 1D- -v k+1 +1， ，易知易知D1 1为为k阶竞赛图，阶竞赛图， 由归纳假设可知，由归纳假设可知，D1 1存在哈密顿通路，存在哈密顿通路， 设设1 1v 1 1v 2 2v k为其中一条。为其中一条。 欧拉图与哈密顿课件 定理定理15.915.9 下面证明下面证明vk+1 +1可扩到 可扩到1 1中去。中去。 若存在若存在v r(1

38、(1rk) )，有有 E( (D) )，i1,2,1,2,r -1-1， 而而 E( (D) )，见左图所示，见左图所示， 则则v 1 1v 2 2v r-1 -1v k+1 +1v r v k为为D中哈密顿通路。中哈密顿通路。 否则否则 i1,2,1,2,k ，均有均有 E( (D) )，见右图所示，见右图所示， 则则 为 为D中哈密顿通路。中哈密顿通路。 欧拉图与哈密顿课件 例例15.615.6 下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？ (1)(1)存在哈密顿回路，所以存在哈密顿回路，所以(1)(1)为哈密顿图。为哈密顿图。

39、(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可可 知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。 欧拉图与哈密顿课件 15.3 15.3 带权图与货郎担问题带权图与货郎担问题 定义定义15.31

40、5.3 给定图给定图G (G为无向图或有向图为无向图或有向图) )，设，设W： ER( (R为实数集为实数集) )，对，对G中任意的边中任意的边e( (vi, ,vj)()(G为有向图为有向图 时，时，e )，设设W( (e) )wij，称实数称实数wij为边为边e上的权，并上的权，并 将将wij标注在边标注在边e上，称上，称G为为带权图带权图，此时常将带权图，此时常将带权图G记作记作 。 )E(Ge W(e) )E(Ge W(e) 设设G G， 称称W( (e) )为为G 的权，并记作的权，并记作W( (G ) )， 即即 W( (G ) ) 带权图应用的领域是相当广泛的，许多图论算法都是针带权图应用的领域是相当广泛的，许多图论算法都是针 对带权图的。对带权图的。 欧拉图与哈密顿课件 货郎担问题货郎担问题 q 设有设有n个城市，城市之间均有道路，道路的长度均大于或等于个城市，城市之间均有道路，道路的长度均大于或等于 0 0，可能是，可能是（对应关联的城市之间无交通线）。一个旅行商（对应关联的城市之间无交通线）。一个旅行商 从某个城市出发，要从某个城市出发，要经过每个城市一次且仅一次经过每个城市一次且仅一次，最后回到，最后回到 出发的城市，问他如何走才能使他出发的城市，问他如何走才能使他走的路线最短走的路线最短？ 这就是著名的这就是著名的旅行商问题旅行商问题或或货郎担问题