欧拉图与哈密顿图-PPT.ppt

《欧拉图与哈密顿图-PPT.ppt》由会员分享，可在线阅读，更多相关《欧拉图与哈密顿图-PPT.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1515章章 欧拉图与哈密顿图欧拉图与哈密顿图离离 散散 数数 学学本章内容本章内容本章内容本章内容15.1 15.1 欧拉图欧拉图15.2 15.2 哈密顿图哈密顿图2 215.1 15.1 15.1 15.1 欧拉图欧拉图欧拉图欧拉图q历史背景哥尼斯堡七桥问题历史背景哥尼斯堡七桥问题q欧拉图是一笔画出的边不重复的回路欧拉图是一笔画出的边不重复的回路。3 3 通通路路:设设G为为无无向向标标定定图图，G中中顶顶点点与与边边的的交交替替序序列列 vi0ej1vi1ej2vi2ejivil称称为为vi0到到vil的的通通路路，其其中中，vi0，vil分分别别称称为为的的始点与终点。始点与终点

2、。回路回路:若若vi0vil，则称通路为回路。，则称通路为回路。简单通路简单通路:通路中，若通路中，若的所有边各异的所有边各异;简单回路简单回路:简单通路中，若简单通路中，若vi0vil；初级通路或路径：若初级通路或路径：若的所有顶点的所有顶点(除除vi0 0与与vij可能相同外可能相同外)各异，各异，所有边也各异；所有边也各异；初级回路或圈初级回路或圈：初级通路或路径中，若初级通路或路径中，若vi0 0vil，15.1 15.1 15.1 15.1 欧拉图欧拉图欧拉图欧拉图4 4欧拉图欧拉图欧拉图欧拉图 欧拉通路欧拉通路:通过图（无向图或有向图）中所有边一次且仅通过图（无向图或有向图）中所有

3、边一次且仅 一次行遍图中所有顶点的通路一次行遍图中所有顶点的通路;欧拉回路欧拉回路:通过图中所有边一次并且仅一次行遍所有顶点通过图中所有边一次并且仅一次行遍所有顶点 的回路。的回路。欧拉图欧拉图:具有欧拉回路的图具有欧拉回路的图;半欧拉图半欧拉图:具有欧拉通路而无欧拉回路的图。具有欧拉通路而无欧拉回路的图。5 5举例举例举例举例欧拉图欧拉图半欧拉图半欧拉图无欧拉通路无欧拉通路欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路6 6无向欧拉图的判定定理无向欧拉图的判定定理无向欧拉图的判定定理无向欧拉图的判定定理 定理定理15.1 15.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通

4、图，且是连通图，且G中没有奇中没有奇度顶点。度顶点。定理定理15.2 15.2 无向图无向图G G是半欧拉图当且仅当是半欧拉图当且仅当G G是连通的，且是连通的，且G G中恰有中恰有两个奇度顶点。两个奇度顶点。7 7大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点9 9有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理定理定理15.3 15.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶点的是强连通的且每个顶点的入度都等于出度。入

5、度都等于出度。定理定理15.4 15.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中中恰有两个奇度顶点，其中一个的入度比出度大恰有两个奇度顶点，其中一个的入度比出度大1 1，另一个的出，另一个的出度比入度大度比入度大1 1，而其余顶点的入度都等于出度。，而其余顶点的入度都等于出度。举例举例1414有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理定理定理15.5 15.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干个边是连通的且为若干个边不重的圈的并。不重的圈的并。1515例例例例15.1 1

6、5.1 15.1 15.1 例例15.1 15.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边边-连通图。连通图。1616例例例例15.1 15.1 15.1 15.1 例例15.1 15.1 设设G是非平凡的且非环的欧拉图，

7、证明：是非平凡的且非环的欧拉图，证明：(1)(1)(G)2)2。(2)(2)对于对于G中任意两个不同顶点中任意两个不同顶点u,v，都存在简单回路都存在简单回路C含含u和和v。证明证明(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与与2

8、 2边不重，边不重，这说明这说明u,v处于处于1 12 2形成的简单回路上。形成的简单回路上。1717求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法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)除非无别的边可供行遍，否则除非无别的边可供行遍，否

9、则ei+1+1不应该为不应该为 GiG-e1 1,e2 2,ei 中的桥。中的桥。(3)(3)当当(2)(2)不能再进行时，算法停止。不能再进行时，算法停止。1818FleuryFleuryFleuryFleury算法示例算法示例算法示例算法示例1919例例例例15.215.215.215.2 对于欧拉图对于欧拉图G，某人用某人用Fleury算法求算法求G中的欧拉回路时，走了简中的欧拉回路时，走了简单回路单回路v2 2e2 2v3 3e3 3v4 4e1414v9 9e1010v2 2e1 1v1 1e8 8v8 8e9 9v2 2之后，无法行遍了，试分析之后，无法行遍了，试分析在哪步他犯了错

10、误在哪步他犯了错误?解答解答 此人行遍此人行遍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，他没有他没有走，所以犯了错误。走，所以犯了错误。2020例例例例15.215.215.215.2 解答：此人行遍解答：此人行遍v8 8时犯了能不走桥就不走

11、时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。桥的错误，因而他没行遍出欧拉回路。当他走到当他走到v8 8时，时，G-e2 2,e3 3,e1414,e1010,e1 1,e8 8 为为下图所示。下图所示。注意：此人在行遍中，在注意：此人在行遍中，在v3 3遇到过桥遇到过桥e3 3，v1 1处遇到过桥处遇到过桥e8 8，但当时除桥外无别的边可但当时除桥外无别的边可走，所以当时均走了桥，这是不会犯错误走，所以当时均走了桥，这是不会犯错误的。的。对于欧拉图对于欧拉图G，某人用某人用Fleury算法求算法求G中的欧拉回路时，中的欧拉回路时，走了简单回路走了简单回路v2e2v3e3v4e14v9

12、e10v2e1v1e8v8e9v2之后，无法之后，无法行遍了，试分析在哪步他犯了错误行遍了，试分析在哪步他犯了错误?212115.2 15.2 15.2 15.2 哈密顿图哈密顿图哈密顿图哈密顿图q历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图2222哈密顿图哈密顿图哈密顿图哈密顿图 定义定义15.2 15.2 经过图（有向图或无向图）中所有顶点一次且仅一经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图

13、称为哈密顿图，有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。平凡图是哈密顿图。说明说明哈密顿通路是图中生成的初级通路，哈密顿回路是生成哈密顿通路是图中生成的初级通路，哈密顿回路是生成的初级回路。的初级回路。判断一个图是否为哈密顿图，就是判断能否将图中所有顶点判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路都放置在一个初级回路(圈圈)上，但这不是一件易事。上，但这不是一件易事。与判断一个图是否为欧拉图不一样，到目前为止，人们还没与判断一个图是否为欧拉图不一样，到目前为

14、止，人们还没有找到哈密顿图简单的充分必要条件。有找到哈密顿图简单的充分必要条件。2323例题例题例题例题(1)(2)(1)(2)是哈密顿图。是哈密顿图。(3)(3)是半哈密顿图。是半哈密顿图。(4)(4)既不是哈密顿图，也不是半哈密顿图。既不是哈密顿图，也不是半哈密顿图。2424定理定理定理定理15.6 15.6 15.6 15.6 定理定理15.6 15.6 设无向图设无向图G 是哈密顿图，对于任意是哈密顿图，对于任意V1 1 V，且且V1 1，均有均有p(G-V1 1)|)|V1 1|其中，其中，p(G-V1 1)为为G-V1 1的连通分支数。的连通分支数。证明证明 设设C为为G中任意一条

15、哈密顿回路，中任意一条哈密顿回路，易知，当易知，当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|。说明说明本定理的条件是哈密顿图的必要条件，但不是充分条件。本定理的条件是哈密顿图的必要条件，但不是充分条件。可以验证彼得松图满足定理中的条件，但不是哈密顿图。可以验证彼得

16、松图满足定理中的条件，但不是哈密顿图。若一个图不满足定理中的条件，它一定不是哈密顿图。若一个图不满足定理中的条件，它一定不是哈密顿图。2525推论推论推论推论 推论推论 设无向图设无向图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

17、-V1 1)p(G -V1 1-(-(u,v)p(G -V1 1)+1)+1|V1 1|+1|+1 2626例例例例15.315.315.315.3例例15.3 15.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不是哈密不是哈密顿图，也

18、不是半哈密顿图。顿图，也不是半哈密顿图。2727例例例例15.315.315.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,h,e，V2 2 b,d,i,j,f，G3 3中存在哈密顿回路。中存在哈密顿回

19、路。如如 abcdgihjefa，所以所以G3 3是哈密顿图。是哈密顿图。2828例例例例15.315.315.315.3的说明的说明的说明的说明q哈密顿通路是经过图中所有顶点的一条初级通路。哈密顿通路是经过图中所有顶点的一条初级通路。q哈密顿回路是经过图中所有顶点的初级回路。哈密顿回路是经过图中所有顶点的初级回路。q对于二部图还能得出下面结论：对于二部图还能得出下面结论：一般情况下，设二部图一般情况下，设二部图G ，|V1 1|V2 2|，且且|V1 1|2|2，|V2 2|2|2，由定理由定理15.615.6及其推论可以得出下面结论：及其推论可以得出下面结论：(1)(1)若若G是哈密顿图，

20、则是哈密顿图，则|V1 1|V2 2|。(2)(2)若若G是半哈密顿图，则是半哈密顿图，则|V2 2|V1 1|+1|+1。(3)(3)若若|V2 2|V1 1|+2|+2，则则G G不是哈密顿图，也不是半哈密顿图。不是哈密顿图，也不是半哈密顿图。例例15.4 15.4 设设G是是n阶无向连通图。证明：若阶无向连通图。证明：若G中有割点或桥，则中有割点或桥，则G不是不是哈密顿图。哈密顿图。证明证明 可用定理可用定理15.615.6证明。证明。2929例例例例15.415.415.415.4例例15.4 15.4 设设G是是n阶无向连通图。证明：若阶无向连通图。证明：若G中有割点或桥，则中有割点

21、或桥，则G不不是哈密顿图。是哈密顿图。证明证明(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中至少有一个，比如中至少有一个，比如

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

23、有两个连通分支，设设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必为连通图。必为连通图。3131定理定理定理定理15.715.715.715.7的推论的推论的推论的推论推论推论 设设G为为n(n3)3)阶无向简单图，若对于阶无向简单图，若对于G中任意两个不相邻的顶中任意两个不相邻的

24、顶点点vi,vj，均有均有 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)类似，可类似，可证明存在过证明存在过上各顶点的圈，上各顶点

25、的圈，此圈即为此圈即为G中的哈密顿回路。中的哈密顿回路。3535例例例例15.515.515.515.5例例15.5 15.5 在在某某次次国国际际会会议议的的预预备备会会议议中中，共共有有8 8人人参参加加，他他们们来来自自不不同同的的国国家家。已已知知他他们们中中任任何何两两个个无无共共同同语语言言的的人人中中的的每每一一个个，与与其其余余有有共共同同语语言言的的人人数数之之和和大大于于或或等等于于8 8，问问能能否否将将这这8 8个个人人排排在在圆桌旁，使其任何人都能与两边的人交谈。圆桌旁，使其任何人都能与两边的人交谈。解答解答 设设8 8个人分别为个人分别为v1 1,v2 2,v8 8

26、，作无向简单图作无向简单图G ，其中其中V v1 1,v2 2,v8 8，vi,vjV，且且ij，若若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中一条哈密顿回路，中一条哈密顿回路

27、，按这条回路的顺序安排座次即可。按这条回路的顺序安排座次即可。哈密顿图是能将图中所有顶哈密顿图是能将图中所有顶点都能安排在某个初级回路点都能安排在某个初级回路上的图。上的图。3737定理定理定理定理15.915.915.915.9定理定理15.9 15.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

28、为为k阶竞赛图，阶竞赛图，由归纳假设可知，由归纳假设可知，D1 1存在哈密顿通路，存在哈密顿通路，设设1 1v 1 1v 2 2v k为其中一条。为其中一条。3838例例例例15.615.615.615.6下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？(1)(1)存在哈密顿回路，所以存在哈密顿回路，所以(1)(1)为哈密顿图。为哈密顿图。(2)(2)取取V1 1 a,b,c,d,e，从图中删除从图中删除V1 1得得7 7个连通分支，个连通分支，由定理由定理15.615.6和推论可知，不是哈密顿图，也不是半哈密顿图。和推论可知，不是哈密顿

29、图，也不是半哈密顿图。(3)(3)取取V1 1 b,e,h，从图中删除从图中删除V1 1得得4 4个连通分支，由定理个连通分支，由定理15.615.6可可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。4040基本要求基本要求基本要求基本要求q深刻理解欧拉图与半欧拉图的定义及判别定理。深刻理解欧拉图与半欧拉图的定义及判别定理。q会用会用Fleury算法求出欧拉图中的欧拉回路。算法求出欧拉图中的欧拉回路。q深刻理解哈密顿图及半哈密顿图的定义。深刻理解哈密顿图及半哈密顿图的定义。q会用破坏哈密顿图应满足的某些必要条件的方法判断某些会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。图不是哈密顿图。q会用满足哈密顿图的充分条件的方法判断某些图是哈密顿会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。图。q严格地分清哈密顿图必要条件和充分条件，千万不能将必严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要要条件当充分条件，同样地，也不能将充分条件当成必要条件。条件。4141作业作业作业作业习题十五习题十五 2 2、6 6 4242