《离散数学欧拉图与哈密顿图.ppt》由会员分享，可在线阅读，更多相关《离散数学欧拉图与哈密顿图.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1515章章 二部图、欧拉图与哈密顿图二部图、欧拉图与哈密顿图离离 散散 数数 学学江苏科技大学本科生必修课程江苏科技大学本科生必修课程计算机系计算机系计算机系计算机系 周塔周塔周塔周塔二部图二部图 q从本节起将讨论一些特殊的图从本节起将讨论一些特殊的图,首先讨论二部图。首先讨论二部图。q定义定义8.418.41若无向图若无向图G G=V V,E E的顶点集合的顶点集合V V可以划分成两个可以划分成两个子集子集X X和和Y Y,使使G G中的每一条边中的每一条边e e的一个端点在的一个端点在X X中中,另一个端点另一个端点在在Y Y中中,则称则称G G为为二部图二部图或或偶图偶图。二部图可
2、记为。二部图可记为G G=X,X,E,YE,Y,X,X和和Y Y称为互补结点子集。称为互补结点子集。q由定义可知由定义可知,二部图不会有自回路。二部图不会有自回路。q定义定义8.42 8.42 二部图二部图G G=X,X,E E,Y Y中中,若若X X的每一的每一顶点都与顶点都与Y Y的每一顶点邻接的每一顶点邻接,则称则称G G为完全二部图为完全二部图,记为记为K Km m,n n,这里这里m m=X X,n n=Y Y。q图图8.418.41给出给出K K2 2,4 4和和K K3 3,3 3的图示。的图示。图 8.41 q定理定理8.418.41无向图无向图G G=V V,E E为二部图的
3、充分必为二部图的充分必要条件为要条件为G G中所有回路的长度均为偶数。中所有回路的长度均为偶数。q定义定义8.438.43给定一个二部图给定一个二部图G G=X,X,E E,Y Y,如果如果E E的子集的子集M M中的边无公共端点中的边无公共端点,则称则称M M为二部图为二部图G G的一个匹的一个匹配。含有最多边数的匹配称为配。含有最多边数的匹配称为G G的最大匹配。的最大匹配。q例例如如,下下图图中中,M M=(=(x x1 1,y,y5 5),(),(x x3 3,y,y1 1),(),(x x4 4,y,y3 3)是是G G的的一一个个匹配。匹配。15.1 15.1 欧拉图欧拉图q历史背
4、景哥尼斯堡七桥问题历史背景哥尼斯堡七桥问题q欧拉图是一笔画出的边不重复的回路欧拉图是一笔画出的边不重复的回路。欧拉图欧拉图定义定义15.115.1 通过图（无向图或有向图）中通过图（无向图或有向图）中所有边一次且仅一次所有边一次且仅一次行遍图中所有顶点的通路称为行遍图中所有顶点的通路称为欧拉通路欧拉通路，通过图中所有边一，通过图中所有边一次并且仅一次行遍所有顶点的次并且仅一次行遍所有顶点的回路回路称为称为欧拉回路欧拉回路。具有欧拉。具有欧拉回路的图称为回路的图称为欧拉图欧拉图，具有欧拉通路而无欧拉回路的图称为，具有欧拉通路而无欧拉回路的图称为半欧拉图半欧拉图。说明说明欧拉通路是图中经过所有边的
5、简单的生成通路欧拉通路是图中经过所有边的简单的生成通路(经过所经过所有顶点的通路称为有顶点的通路称为生成通路生成通路)。欧拉回路是经过所有边的简单的生成回路。欧拉回路是经过所有边的简单的生成回路。举例举例欧拉图欧拉图半欧拉图半欧拉图无欧拉通路无欧拉通路欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路无向欧拉图的判定定理无向欧拉图的判定定理无向欧拉图的判定定理无向欧拉图的判定定理 定理定理15.115.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通图，且是连通图，且G中没有奇度顶点。中没有奇度顶点。定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连
6、通的，且是连通的，且G中恰有两个奇度顶点。中恰有两个奇度顶点。半欧拉图的判定定理半欧拉图的判定定理半欧拉图的判定定理半欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理有向欧拉图的判定定理定理定理15.315.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶点的是强连通的且每个顶点的入度都等于出度。入度都等于出度。定理定理15.415.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中中恰有两个奇度顶点，其中一个的入度比出度大恰有两个奇度顶点，其中一个的入度比出度大1 1，另一个的出，另一个的出度比入度大
7、度比入度大1 1，而其余顶点的入度都等于出度。，而其余顶点的入度都等于出度。(举例举例)定理定理15.515.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通的且为若干个边是连通的且为若干个边不重的圈的并。不重的圈的并。15.2 15.2 哈密顿图哈密顿图q历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图哈密顿周游世界问题哈密顿周游世界问题q哈密顿圈是图论中著名世界难题之一。哈密顿圈是图论中著名世界难题之一。q“18591859年，英国数学家兼物理学家哈密顿提出以年，英国数学家兼物理学家哈密顿提出以下周游世界问题：用一个正十二面体的二十个顶点下周游世界
8、问题：用一个正十二面体的二十个顶点表示二十个城市，怎样才能从一个城市出发，沿着表示二十个城市，怎样才能从一个城市出发，沿着棱经过每个城市恰好一次，最后返回到出发点？棱经过每个城市恰好一次，最后返回到出发点？哈密顿图哈密顿图 定义定义15.215.2 经过图（有向图或无向图）中经过图（有向图或无向图）中所有顶点一次且仅一所有顶点一次且仅一次的通路次的通路称为称为哈密顿通路哈密顿通路。经过图中。经过图中所有顶点一次且仅一次所有顶点一次且仅一次的回路的回路称为称为哈密顿回路哈密顿回路。具有哈密顿回路的图称为。具有哈密顿回路的图称为哈密顿图哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为具有哈密顿通
9、路但不具有哈密顿回路的图称为半哈密顿图半哈密顿图。规定：平凡图是哈密顿图。规定：平凡图是哈密顿图。说明说明哈密顿通路是图中生成的初级通路，哈密顿通路是图中生成的初级通路，哈密顿回路是生成的初级回路。哈密顿回路是生成的初级回路。判断一个图是否为哈密顿图，就是判断能否将图中所有顶点判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路都放置在一个初级回路(圈圈)上，但这不是一件易事。上，但这不是一件易事。与判断一个图是否为欧拉图不一样，到目前为止，人们还没与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。有找到哈密顿图简单的充分必要条件。例题例
10、题(1)(2)(1)(2)是哈密顿图。是哈密顿图。(3)(3)是半哈密顿图。是半哈密顿图。(4)(4)既不是哈密顿图，也不是半哈密顿图。既不是哈密顿图，也不是半哈密顿图。推论推论 推论推论1 1 设无向图设无向图G 是哈密顿图，对于任意的是哈密顿图，对于任意的V1 1 V且且V1 1，均有均有 p(G-V1 1)|)|V1 1|推论推论2 2 设无向图设无向图G 是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 1 V且且V1 1，均有均有 p(G-V1 1)|)|V1 1|+1|+1例例15.315.3例例15.315.3 在下图中给出的三个图都是二部图。它们中的哪些是在下图中给出的三个
11、图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？哈密顿图？哪些是半哈密顿图？为什么？易知互补顶点子集易知互补顶点子集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|
12、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中存在哈密顿回路。中存在哈密顿回路。如如 abcdgihjefa，所以所以G3 3是哈密顿图。是哈密顿图。例例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可可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。