离散数学欧拉图与哈密顿图.ppt

第15章 二部图、欧拉图与哈密顿图,离 散 数 学,江苏科技大学本科生必修课程,计算机系 周塔,二部图,从本节起将讨论一些特殊的图,首先讨论二部图。定义8.41若无向图G=V,E的顶点集合V可以划分成两个子集X和Y,使G中的每一条边e的一个端点在X中,另一个端点在Y中,则称G为二部图或偶图。二部图可记为G=X,E,Y,X和Y称为互补结点子集。由定义可知,二部图不会有自回路。,定义8.42 二部图G=X,E,Y中,若X的每一顶点都与Y的每一顶点邻接,则称G为完全二部图,记为Km,n,这里m=X,n=Y。图8.41给出K2,4和K3,3的图示。,图 8.41,定理8.41无向图G=V,E为二部图的充分必要条件为G中所有回路的长度均为偶数。,定义8.43给定一个二部图G=X,E,Y,如果E的子集M中的边无公共端点,则称M为二部图G的一个匹配。含有最多边数的匹配称为G的最大匹配。例如,下图中,M=(x1,y5),(x3,y1),(x4,y3)是G的一个匹配。,15.1 欧拉图,历史背景哥尼斯堡七桥问题,欧拉图是一笔画出的边不重复的回路。,欧拉图,定义15.1 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。说明欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。欧拉回路是经过所有边的简单的生成回路。,举例,欧拉图,半欧拉图,无欧拉通路,欧拉图,无欧拉通路,无欧拉通路,无向欧拉图的判定定理,定理15.1 无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。,定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。,半欧拉图的判定定理,有向欧拉图的判定定理,定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。(举例),定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。,15.2 哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,哈密顿周游世界问题,哈密顿圈是图论中著名世界难题之一。“1859年，英国数学家兼物理学家哈密顿提出以下周游世界问题：用一个正十二面体的二十个顶点表示二十个城市，怎样才能从一个城市出发，沿着棱经过每个城市恰好一次，最后返回到出发点？,哈密顿图,定义15.2 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。规定：平凡图是哈密顿图。说明哈密顿通路是图中生成的初级通路，哈密顿回路是生成的初级回路。判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路(圈)上，但这不是一件易事。与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。,例题,(1)(2)是哈密顿图。(3)是半哈密顿图。(4)既不是哈密顿图，也不是半哈密顿图。,推论,推论1 设无向图G是哈密顿图，对于任意的V1V且V1，均有 p(G-V1)|V1|推论2 设无向图G是半哈密顿图，对于任意的V1V且V1，均有 p(G-V1)|V1|+1,例15.3,例15.3 在下图中给出的三个图都是二部图。它们中的哪些是哈密顿图？哪些是半哈密顿图？为什么？,易知互补顶点子集V1a,fV2b,c,d,e设此二部图为G1，则G1。p(G1-V1)4|V1|2，由定理15.6及其推论可知，G1不是哈密顿图，也不是半哈密顿图。,例15.3,设图为G2，则G2，其中V1a,g,h,i,c，V2b,e,f,j,k,d，易知，p(G2-V1)|V2|6|V1|5，由定理15.6可知，G2不是哈密顿图，但G2是半哈密顿图。baegjckhfid为G2中一条哈密顿通路。,设图为G3。G3，其中V1a,c,g,h,e，V2b,d,i,j,f，G3中存在哈密顿回路。如 abcdgihjefa，所以G3是哈密顿图。,例15.6,下图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？,(1)存在哈密顿回路，所以(1)为哈密顿图。,(2)取V1a,b,c,d,e，从图中删除V1得7个连通分支，由定理15.6和推论可知，不是哈密顿图，也不是半哈密顿图。,(3)取V1b,e,h，从图中删除V1得4个连通分支，由定理15.6可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。,