离散数学：15欧拉图与哈密顿图

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

2、图中所有边，通过图中所有边一次并且仅一次行遍所有顶点的一次并且仅一次行遍所有顶点的回路回路称为称为欧拉回路欧拉回路。具有。具有欧拉回路的图称为欧拉回路的图称为欧拉图欧拉图，具有欧拉通路而无欧拉回路的，具有欧拉通路而无欧拉回路的图称为图称为半欧拉图半欧拉图。 说明说明欧拉通路是图中经过所有边的简单的生成通路欧拉通路是图中经过所有边的简单的生成通路( (经过所经过所有顶点的通路称为生成通路有顶点的通路称为生成通路) )。欧拉回路是经过所有边的简单的生成回路。欧拉回路是经过所有边的简单的生成回路。 规定平凡图为欧拉图规定平凡图为欧拉图 环不影响图的欧拉性环不影响图的欧拉性 5举例举例欧拉图欧拉图半欧

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

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

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

6、且无奇度顶点，条边，且无奇度顶点，并且设并且设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，最后回到最后回到vr，得回路得回路vrv* *j1 1v* *j1 1v* *j

7、2 2v* *j2 2v* *jsv* *jsvr，此回路经过此回路经过G中每条边一次且仅一次并行遍中每条边一次且仅一次并行遍G中所有顶点，中所有顶点，因而它是因而它是G中的欧拉回路（中的欧拉回路（演示这条欧拉回路演示这条欧拉回路），），故故G为欧拉图。为欧拉图。 9归纳法证明示意图归纳法证明示意图 10定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通的，且是连通的，且G中恰有两中恰有两个奇度顶点。个奇度顶点。证明证明 必要性必要性。设。设G是是m条边的条边的n阶无向图，因为阶无向图，因为G为半欧拉图，为半欧拉图，因而因而G中存在欧拉通路中存在欧拉通路( (

8、但不存在欧拉回路但不存在欧拉回路) )，设设vi0 0ej1 1vi1 1vim-1-1ejmvim为为G中一条欧拉通路，中一条欧拉通路，vi0 0vim。 vV( (G) )，若若v不在不在的端点出现，显然的端点出现，显然d( (v) )为偶数，为偶数，若若v在端点出现过，则在端点出现过，则d( (v) )为奇数，为奇数，因为因为只有两个端点且不同，因而只有两个端点且不同，因而G中只有两个奇数顶点。中只有两个奇数顶点。另外，另外，G的连通性是显然的。的连通性是显然的。半欧拉图的判定定理半欧拉图的判定定理 11定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通

9、的，且是连通的，且G中恰有两中恰有两个奇度顶点。个奇度顶点。证明证明 充分性充分性。设。设G的两个奇度顶点分别为的两个奇度顶点分别为u0 0和和v0 0，对对G加新边（加新边（u0 0, ,v0 0），），得得G G(u0 0, ,v0 0) )，则则G 是连通且无奇度顶点的图，是连通且无奇度顶点的图，由定理由定理15.115.1可知，可知，G 为欧拉图，为欧拉图，因而存在欧拉回路因而存在欧拉回路C ，而而CC -(-(u0 0, ,v0 0) )为为G中一条欧拉通路，中一条欧拉通路，所以所以G为半欧拉图。为半欧拉图。 半欧拉图的判定定理半欧拉图的判定定理 12有向欧拉图的判定定理有向欧拉图的

10、判定定理定理定理15.315.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶点的是强连通的且每个顶点的入度都等于出度。入度都等于出度。定理定理15.415.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是是单向连通的，且单向连通的，且D中中恰有两个奇度顶点，其中一个的入度比出度大恰有两个奇度顶点，其中一个的入度比出度大1 1，另一个的出，另一个的出度比入度大度比入度大1 1，而其余顶点的入度都等于出度。，而其余顶点的入度都等于出度。( (举例举例) )定理定理15.515.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干个边是连通的且为

11、若干个边不重的圈的并。不重的圈的并。 13例例15.115.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中，中，因而因而p( (G- -e) )p( (G) )，故故e不是桥。不是桥。由由e的任意性的任意性(G)2)2，即即G是是2 2边边- -连通图。连通图。(2)(2) u, ,vV(

12、(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与与 2 2边不重，边不重，这说明这说明u, ,v处于处于 1 1 2 2形成的简单回路上。形成的简单回路上。 14求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法Fleury算法

13、算法，能不走桥就不走桥能不走桥就不走桥 (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) 除非无别的边可供行遍，否则除非无别的边可供行遍，否则ei+1+1不应该为不应该为 GiG-e1 1, ,e2 2, , ,ei 中的桥。中的桥。(3)(3)当当(2)(2)不能再进行时，算法停止。不能再进行时，算法停止

14、。 说明说明可以证明，当算法停止时所得简单回路可以证明，当算法停止时所得简单回路Pmv0 0e1 1v1 1e2 2emvm( (vmv0 0) )为为G中一条欧拉回路。中一条欧拉回路。 15FleuryFleury算法示例算法示例 16例例15.215.2下图是给定的欧拉图下图是给定的欧拉图G。某人用某人用Fleury算法求算法求G中的欧拉回路时中的欧拉回路时，走了简单回路，走了简单回路v2 2e2 2v3 3e3 3v4 4e1414v9 9e1010v2 2e1 1v1 1e8 8v8 8e9 9v2 2之后之后( (观看他的观看他的错误走法错误走法) )，无法行遍了，试分析在哪步他犯了

15、错误，无法行遍了，试分析在哪步他犯了错误? ? 解答解答 此人行遍此人行遍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遇到

16、过桥遇到过桥e3 3，v1 1处遇到过桥处遇到过桥e8 8，但当时除桥外他无别的边可走，所但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。以当时均走了桥，这是不会犯错误的。 17q 例例 在下图中，恰有两个奇结点在下图中，恰有两个奇结点4 4和和9 9，故存在，故存在EulerEuler路，按路，按照照FleuryFleury算法可得其中一条算法可得其中一条EulerEuler路为路为: :q ( (9,7,8,9,10,11,12,10,3,2,1,3,4,5,6,4)9,7,8,9,10,11,12,10,3,2,1,3,4,5,6,4)。127893456111210 1

17、8q HamiltonHamilton爵士（爵士（1805180518651865）在）在18591859年发明了一种游戏，年发明了一种游戏，用一个正实心的十二面体，它的二十个顶点标有二十个城用一个正实心的十二面体，它的二十个顶点标有二十个城市的名字，要求游戏者找一条沿着各边通过每个顶点一次市的名字，要求游戏者找一条沿着各边通过每个顶点一次且仅一次的闭合回路，即绕行世界问题。且仅一次的闭合回路，即绕行世界问题。HamiltonHamilton以以2525个个金币的代价将他的设计卖给了一个玩具商。金币的代价将他的设计卖给了一个玩具商。q 由于正十二面体是由由于正十二面体是由1212个相同的正五边

18、形组成，且有个相同的正五边形组成，且有2020个个顶点，该问题为怎样才能沿着顶点，该问题为怎样才能沿着1212面体的棱旅行，经过每个面体的棱旅行，经过每个城市恰好一次，然后回到家中。城市恰好一次，然后回到家中。HamiltonHamilton给出了这个问题给出了这个问题的肯定的答复。的肯定的答复。15.2 15.2 哈密顿图哈密顿图 19 (1) (2) 图图5 20哈密顿图哈密顿图 定义定义15.215.2 经过图（有向图或无向图）中经过图（有向图或无向图）中所有顶点一次且仅一所有顶点一次且仅一次的通路次的通路称为称为哈密顿通路哈密顿通路。经过图中。经过图中所有顶点一次且仅一所有顶点一次且仅

19、一次的回路次的回路称为称为哈密顿回路哈密顿回路。具有哈密顿回路的图称为。具有哈密顿回路的图称为哈密哈密顿图顿图，具有哈密顿通路但不具有哈密顿回路的图称为，具有哈密顿通路但不具有哈密顿回路的图称为半哈半哈密顿图密顿图。平凡图是哈密顿图。平凡图是哈密顿图。说明说明哈密顿通路是图中生成的初级通路，哈密顿通路是图中生成的初级通路，哈密顿回路是生成的初级回路。哈密顿回路是生成的初级回路。判断一个图是否为哈密顿图，就是判断能否将图中所有顶判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路点都放置在一个初级回路( (圈圈) )上，但这不是一件易事。上，但这不是一件易事。与判断一个图是否

20、为欧拉图不一样，到目前为止，人们还与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。没有找到哈密顿图简单的充分必要条件。 21例题例题(1)(2)(1)(2)是哈密顿图。是哈密顿图。(3)(3)是半哈密顿图。是半哈密顿图。(4)(4)既不是哈密顿图，也不是半哈密顿图。既不是哈密顿图，也不是半哈密顿图。 22定理定理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

21、 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| |。说明说明本定理的条件

22、本定理的条件是哈密顿图的必要条件，但不是充分条件。是哈密顿图的必要条件，但不是充分条件。可以验证彼得松图满足定理中的条件，但不是哈密顿图。可以验证彼得松图满足定理中的条件，但不是哈密顿图。若一个图不满足定理中的条件，它一定不是哈密顿图。若一个图不满足定理中的条件，它一定不是哈密顿图。 23推论推论 推论推论 设无向图设无向图G 是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 1 V且且V1 1，均有均有 p( (G- -V1 1)|)|V1 1|+1 |+1 证明证明 设设P是是G中起于中起于u终于终于v的哈密顿通路，的哈密顿通路，令令G G(u, ,v)()(在在G的顶点的顶点u, ,

23、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 24例例15.315.3例例15.315.3 在下图中给出的三个图都是二部图。它们中的哪些是在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？哈密顿图？哪些是半哈密顿图？为什么？易知互补顶点子集易知互补顶点子集V1 1 a, ,f V2 2 b, ,

24、c, ,d, ,e 设此二部图为设此二部图为G1 1，则则G1 1 。p( (G1 1- -V1 1) )4|4|V1 1| |2 2，由由定理定理15.615.6及其推论可知，及其推论可知，G1 1不是哈密不是哈密顿图，也不是半哈密顿图。顿图，也不是半哈密顿图。 25例例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不是哈密顿图，

25、不是哈密顿图，但但G2 2是半哈密顿图。是半哈密顿图。baegjckhfid为为G2 2中一条哈密顿通路。中一条哈密顿通路。设图为设图为G3 3。G3 3 ，其中其中V1 1 a, ,c, ,g, ,h, ,e ，V2 2 b, ,d, ,i, ,j, ,f ，G3 3中存在哈密顿回路。中存在哈密顿回路。如如 abcdgihjefa，所以所以G3 3是哈密顿图。是哈密顿图。 26例例15.315.3的说明的说明q 哈密顿通路是经过图中所有顶点的一条初级通路。哈密顿通路是经过图中所有顶点的一条初级通路。q 哈密顿回路是经过图中所有顶点的初级回路。哈密顿回路是经过图中所有顶点的初级回路。 q 对于

26、二部图还能得出下面结论：对于二部图还能得出下面结论： 一般情况下，设二部图一般情况下，设二部图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|+1。( (3) 3) 若若| |V2 2| | |V1 1|+2|+2，则则G G不是哈密顿图，也不是半哈密顿图。不是哈密顿图

27、，也不是半哈密顿图。 例例15.415.4 设设G是是n阶无向连通图。证明：阶无向连通图。证明：若若G中有割点或桥，则中有割点或桥，则G不是不是哈密顿图。哈密顿图。证明证明 可可用定理用定理15.615.6证明。证明。 27例例15.415.4例例15.415.4 设设G是是n阶无向连通图。证明：若阶无向连通图。证明：若G中有割点或桥，则中有割点或桥，则G不不是哈密顿图。是哈密顿图。证明证明(1)(1)证明证明若若G中有割点，则中有割点，则G不是哈密顿图。不是哈密顿图。设设v为连通图为连通图G中一个割点，则中一个割点，则V v 为为G中的点割集，而中的点割集，而p( (G- -V )2)21

28、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不是哈密顿图。不

29、是哈密顿图。 28定理定理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 1V( (G1 1) )，v2 2V( (G2 2) )，因为因为G是简单图，所以是简单图，所以dG(

30、 (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必为连通图。必为连通图。 29定理定理15.715.7下面证下面证G中存在哈密顿通路。中存在哈密顿通路。设设 v1 1v2 2vl为为G中用中用“扩大路径法扩大路径法”得到的得到的“极大路径极大路径”，即即 的始点的始点v1 1与终点与终点vl不与不与 外的顶点相邻。显然有外的顶点相邻。显然有ln。 (1)(1)若若ln，则则 为为G中哈密顿通路。中哈密顿通路。(2)(2)若若ln，这说明这说明

31、 不是哈密顿通路，不是哈密顿通路，即即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

32、-1，这与这与( (15.1)15.1)矛盾矛盾) )此时，此时，vl至少与至少与vi2 2, , ,vik相邻的顶点相邻的顶点vi2-12-1, , ,vik-1-1之一相邻之一相邻( (否则否则 d( (v1 1)+)+d( (vl) )k+ +l-2-(-2-(k-1)-1)l-1-1n-1-1) )设设vl与与vir -1-1相邻（相邻（2 2rk），），见下图所示。见下图所示。于是，回路于是，回路Cv1 1v2 2vir -1-1vlvlr -1-1vivirv1 1过过上的所有顶点。上的所有顶点。 31定理定理15.715.7( (c)c)下面证明存在比下面证明存在比 更长的路径。

33、更长的路径。因为因为l n，所以所以C外还有顶点，由外还有顶点，由G的连通性可知，的连通性可知，存在存在vl+1+1V( (G)-)-V( (C) )与与C上某顶点上某顶点vt相邻，见下图所示。相邻，见下图所示。删除边删除边(vt-1,vt)得路径得路径vt-1v1virvlvir-1vtvl+1比比 长度大长度大1，对对上的顶点重新排序，使其成为上的顶点重新排序，使其成为 v1v2vlvl+1，对对重复重复(a)(c)，在有限步内一定得到在有限步内一定得到G的哈密顿通路。的哈密顿通路。 32q几点说明：几点说明： 定理定理15.7是半哈密顿图的充分条件是半哈密顿图的充分条件, 但不是必要但不

34、是必要条件条件. 长度为长度为n 1(n 4)的路径构成的图不满足的路径构成的图不满足( )条件条件, 但它显然是半哈密顿图但它显然是半哈密顿图. 定理定理15.7的推论同样不是哈密顿图的必要条件的推论同样不是哈密顿图的必要条件, G为长为为长为n的圈的圈, 不满足不满足()条件条件, 但它当然是哈但它当然是哈密顿图密顿图. 由定理由定理15.7的推论可知的推论可知, Kn(n 3)均为哈密顿图均为哈密顿图. 33定理定理15.715.7的推论的推论推论推论 设设G为为n( (n3)3)阶无向简单图，若对于阶无向简单图，若对于G中任意两个不相邻的中任意两个不相邻的顶点顶点vi, ,vj，均有均

35、有 d( (vi)+)+d( (vj) )n(15.2)(15.2)则则G中存在哈密顿回路，从而中存在哈密顿回路，从而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)类似，可类似，可证明存在过证明存在过上各顶点的圈，

36、上各顶点的圈，此圈即为此圈即为G中的哈密顿回路。中的哈密顿回路。 34定理定理15.815.8定理定理15.815.8 设设u, ,v为为n阶无向图阶无向图G中两个不相邻的顶点，且中两个不相邻的顶点，且d( (u)+)+d( (v) )n，则则G为哈密顿图当且仅当为哈密顿图当且仅当G( (u, ,v) )为哈密为哈密顿图顿图( ( (u, ,v) )是加的新边是加的新边) )。 证明证明 必要性：若必要性：若G为哈密顿图，则显然为哈密顿图，则显然G( (u, ,v) )为哈密顿图；为哈密顿图； 充分性：设充分性：设G( (u, ,v) )为哈密顿图，并设为哈密顿图，并设C C为为G( (u,

37、,v) )的的一一个哈密顿回路，若边个哈密顿回路，若边( (u, ,v) )不在不在C C中，则中，则C C也是也是G G的哈密顿回的哈密顿回路。若边路。若边( (u, ,v) )在在C C中，不妨设中，不妨设C=vC=v1 1v v2 2v vn nv v1 1( (其中其中v v1 1=u,v=u,v2 2=v) =v) 下面分两种情况讨论：下面分两种情况讨论： 1: 1: 若存在若存在i(2in)i(2in)，使得，使得u u与与v vi i相邻接，相邻接，v v与与v vi+1i+1相邻接，则相邻接，则G G必有哈密顿回路必有哈密顿回路C=uvC=uvi iv vi-1i-1vvvvi

38、+1i+1v vn nu u 35定理定理15.815.8证明证明 2: 2: 若不存在这样的若不存在这样的i i，则因为，则因为v v3 3v v4 4v vn-1n-1v vn n中有中有d(u)d(u)个结点与个结点与u u相邻，所以在相邻，所以在v v3 3v v4 4v v5 5v vn n中至少有中至少有d(u)d(u)个结点不与个结点不与v v相邻，相邻，因而因而d(v)d(v) n-1-d(u)n-1-d(u)即即d(v)+d(ud(v)+d(u)n )n 矛盾矛盾 V1=uV2=vv3v4viVi+1Vn-1vn 36例例15.515.5例例15.515.5 在某次国际会议的

39、预备会议中，共有在某次国际会议的预备会议中，共有8 8人参加，他们来自不人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于其余有共同语言的人数之和大于或等于8 8，问能否将这，问能否将这8 8个人排在个人排在圆桌旁，使其任何人都能与两边的人交谈。圆桌旁，使其任何人都能与两边的人交谈。 解答解答 设设8 8个人分别为个人分别为v1 1, ,v2 2, , ,v8 8，作无向简单图作无向简单图G ，其中其中V v1 1, ,v2 2, , ,v8 8 ， vi, ,vjV，且且ij，若

40、若vi与与vj有共同语言，就在有共同语言，就在vi, ,vj之间连无向边之间连无向边( (vi, ,vj) )，由此组成边集合由此组成边集合E，则则G为为8 8阶无向简单图，阶无向简单图， viV，d( (vi) )为与为与vi有共同语言的人数。有共同语言的人数。由已知条件可知，由已知条件可知， vi, ,vjV且且ij，均有均有d( (vi)+)+d( (vj) )8 8。由由定理定理15.715.7的推论可知，的推论可知，G中存在哈密顿回路，中存在哈密顿回路，设设Cvi1 1vi2 2vi8 8为为G中一条哈密顿回路，中一条哈密顿回路，按这条回路的顺序安排座次即可。按这条回路的顺序安排座次

41、即可。哈密顿图是能将图中所有顶哈密顿图是能将图中所有顶点都能安排在某个初级回路点都能安排在某个初级回路上的图上的图。 37定理定理15.915.9定理定理15.915.9 若若D为为n( (n2)2)阶阶竞赛图，则竞赛图，则D中具有哈密顿通路。中具有哈密顿通路。 证明证明 对对n作归纳法。作归纳法。n2 2时，时，D的的基图基图为为K2 2，结论成立。结论成立。设设nk时结论成立。现在设时结论成立。现在设nk+1+1。设设V( (D) ) v1 1, ,v2 2, , ,vk, ,vk+1+1 。令令D1 1D- -vk+1+1，易知易知D1 1为为k阶竞赛图，阶竞赛图，由归纳假设可知，由归纳

42、假设可知，D1 1存在哈密顿通路，存在哈密顿通路，设设1 1v 1 1v 2 2v k为其中一条。为其中一条。 38定理定理15.915.9下面证明下面证明vk+1+1可扩到可扩到1 1中去。中去。若存在若存在v r( (1 1rk) )，有有 E( (D) )，i1,2,1,2, ,r -1-1，而而 E( (D) )，见左图所示，见左图所示，则则v 1 1v 2 2v r-1-1vk+1+1v rv k为为D中哈密顿通路。中哈密顿通路。否则否则 i1,2,1,2, ,k ，均有均有 E( (D) )，见右图所示，见右图所示，则则 为为D中哈密顿通路。中哈密顿通路。 39例例15.615.6

43、下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？ ( (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可可知，它不是哈

44、密顿图。但存在哈密顿通路，所以是半哈密顿图。知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。 40 满足定理满足定理15.7推论的条件推论的条件(). 完全图完全图Kn(n 3)中任何两个顶点中任何两个顶点u, v, 均有均有 d(u)+d(v) = 2(n 1) n(n 3), 所以所以Kn为哈密顿图为哈密顿图. 破坏定理破坏定理15.6的条件的图不是哈密顿图的条件的图不是哈密顿图. 例例 在四分之一国际象棋盘在四分之一国际象棋盘(4 4方格组成方格组成)上上跳马无解跳马无解. 在国际象棋盘上跳马有解在国际象棋盘上跳马有解. 41 (1) (2) 图图10 令令V1=a, b, c,

45、 d, 则则p(G V1) = 6 4, 由定理由定理15.6可知图可知图中无哈密顿回路中无哈密顿回路.在国际象棋盘上跳马有解在国际象棋盘上跳马有解, 试试看试试看. 4215.3 15.3 带权图与货郎担问题带权图与货郎担问题定义定义15.315.3 给定图给定图G (G为无向图或有向图为无向图或有向图) )，设，设W：ER( (R为实数集为实数集) )，对，对G中任意的边中任意的边e( (vi, ,vj)()(G为有向图为有向图时，时，e )，设设W( (e) )wij，称实数称实数wij为边为边e上的权，并上的权，并将将wij标注在边标注在边e上，称上，称G为为带权图带权图，此时常将带权

46、图，此时常将带权图G记作记作 。)E(GeW(e)E(GeW(e)设设G G， 称称W( (e) )为为G 的权，并记作的权，并记作W( (G ) )，即即 W( (G ) )带权图应用的领域是相当广泛的，许多图论算法都是针带权图应用的领域是相当广泛的，许多图论算法都是针对带权图的。对带权图的。 43货郎担问题货郎担问题q 设有设有n个城市，城市之间均有道路，道路的长度均大于或等于个城市，城市之间均有道路，道路的长度均大于或等于0 0，可能是，可能是（对应关联的城市之间无交通线）。一个旅行商（对应关联的城市之间无交通线）。一个旅行商从某个城市出发，要从某个城市出发，要经过每个城市一次且仅一次经

47、过每个城市一次且仅一次，最后回到，最后回到出发的城市，问他如何走才能使他出发的城市，问他如何走才能使他走的路线最短走的路线最短？这就是著名的这就是著名的旅行商问题旅行商问题或或货郎担问题货郎担问题。q 这个问题可化归为如下的图论问题。这个问题可化归为如下的图论问题。设设G ，为一个为一个n阶完全带权图阶完全带权图Kn，各边的权非负，各边的权非负，且有的边的权可能为且有的边的权可能为。求求G G中一条最短的哈密顿回路中一条最短的哈密顿回路，这就，这就是货郎担问题的数学模型。是货郎担问题的数学模型。q 此问题中不同哈密顿回路的含义：此问题中不同哈密顿回路的含义：将图中生成圈看成一个哈密顿回路，即不

48、考虑始点将图中生成圈看成一个哈密顿回路，即不考虑始点( (终点终点) )的的区别以及顺时针行遍与逆时针行遍的区别。区别以及顺时针行遍与逆时针行遍的区别。 44例例15.715.7例例15.715.7 下下图为图为4 4阶完全带权图阶完全带权图K4 4。求出它的不同的哈密顿回路求出它的不同的哈密顿回路，并指出最短的哈密顿回路。，并指出最短的哈密顿回路。解答解答 由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿回路从任何顶点出发都可以。下面先求出从回路从任何顶点出发都可以。下面先求出从a a点出发，考虑顺点出发，考虑顺时针与逆时针顺序的不同的哈密

49、顿回路。时针与逆时针顺序的不同的哈密顿回路。C1 1abcda C2 2abdcaC3 3acbdaC4 4acdbaC5 5adbcaC6 6adcba 45带权图的说明带权图的说明q n阶完全带权图中共存在阶完全带权图中共存在( (n-1)!/2-1)!/2种不同的哈密顿回路，经种不同的哈密顿回路，经过比较，可找出最短哈密顿回路。过比较，可找出最短哈密顿回路。q n4 4时，时， 有有3 3种不同哈密顿回路。种不同哈密顿回路。n5 5时，时， 有有1212种，种，n6 6时，时， 有有6060种，种，n7 7时，时， 有有360360种，种，n1010时，有时，有5 59!=1 814 4

50、009!=1 814 400种，种，。q 由此可见货郎担问题的计算量是相当大的。由此可见货郎担问题的计算量是相当大的。q 对于货郎担问题，人们一方面还在寻找好的算法，另一方对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。面也在寻找各种近似算法。 46中国邮递员问题中国邮递员问题q 一名邮递员带着要分发的邮件从邮局出发，经过要分发的一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使走过他管辖范围内的每一条街道，如何选择投递

51、路线，使邮递员走尽可能少的路程。邮递员走尽可能少的路程。q 这个问题是由我国数学家管梅谷先生（山东师范大学数学这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在系教授）在19601960年首次提出的，因此在国际上称之为中国年首次提出的，因此在国际上称之为中国邮递员问题。邮递员问题。q 用图论的述语，在一个连通的赋权图用图论的述语，在一个连通的赋权图G( (V, ,E) )中，要寻找一中，要寻找一条回路，使该回路包含条回路，使该回路包含G中的每条边至少一次，且该回路的中的每条边至少一次，且该回路的权数最小。也就是说要从包含权数最小。也就是说要从包含G G的每条边的回路中找一条权的每条边

52、的回路中找一条权数最小的回路。数最小的回路。 47基本要求基本要求q 深刻理解欧拉图与半欧拉图的定义及判别定理。深刻理解欧拉图与半欧拉图的定义及判别定理。q 会用会用Fleury算法求出欧拉图中的欧拉回路。算法求出欧拉图中的欧拉回路。q 深刻理解哈密顿图及半哈密顿图的定义。深刻理解哈密顿图及半哈密顿图的定义。q 会用破坏哈密顿图应满足的某些必要条件的方法判断某些会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。图不是哈密顿图。q 会用满足哈密顿图的充分条件的方法判断某些图是哈密顿会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。图。q 严格地分清哈密顿图必要条件和充分条件，千万不能将必严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要要条件当充分条件，同样地，也不能将充分条件当成必要条件。条件。 48