1、第第1515章章 二部图、欧拉图与哈密顿图二部图、欧拉图与哈密顿图离离 散散 数数 学学江苏科技大学本科生必修课程江苏科技大学本科生必修课程计算机系计算机系计算机系计算机系 周塔周塔周塔周塔1/19二部图二部图 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由定义可知由定义可知,二部图不会有自回路。二部图不会有自回路。2/19q定义定义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 3/19q定理定理8.418.41无向图无向图G G=V V,E E为二部图充分必
3、为二部图充分必要条件为要条件为G G中全部回路长度均为偶数。中全部回路长度均为偶数。4/19q定义定义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一一个个匹配。匹配。5/1915.1 15.1 欧拉图欧拉图q历史背景哥尼斯堡七桥问
4、题历史背景哥尼斯堡七桥问题q欧拉图是一笔画出边不重复回路欧拉图是一笔画出边不重复回路。6/19欧拉图欧拉图定义定义15.115.1 经过图（无向图或有向图）中经过图（无向图或有向图）中全部边一次且仅一次全部边一次且仅一次行遍图中全部顶点通路称为行遍图中全部顶点通路称为欧拉通路欧拉通路，经过图中全部边一次，经过图中全部边一次而且仅一次行遍全部顶点而且仅一次行遍全部顶点回路回路称为称为欧拉回路欧拉回路。含有欧拉回路。含有欧拉回路图称为图称为欧拉图欧拉图，含有欧拉通路而无欧拉回路图称为，含有欧拉通路而无欧拉回路图称为半欧拉图半欧拉图。说明说明欧拉通路是图中经过全部边简单生成通路欧拉通路是图中经过全部
5、边简单生成通路(经过全部顶经过全部顶点通路称为点通路称为生成通路生成通路)。欧拉回路是经过全部边简单生成回路。欧拉回路是经过全部边简单生成回路。7/19举例举例欧拉图欧拉图半欧拉图半欧拉图无欧拉通路无欧拉通路欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路8/19无向欧拉图判定定理无向欧拉图判定定理无向欧拉图判定定理无向欧拉图判定定理 定理定理15.115.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G是连通图，且是连通图，且G中没有奇度顶点。中没有奇度顶点。9/19定理定理15.215.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G是连通，且是连通，且G中中恰有两个奇度顶
6、点。恰有两个奇度顶点。半欧拉图判定定理半欧拉图判定定理半欧拉图判定定理半欧拉图判定定理10/19有向欧拉图判定定理有向欧拉图判定定理有向欧拉图判定定理有向欧拉图判定定理定理定理15.315.3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通且每个顶点入度是强连通且每个顶点入度都等于出度。都等于出度。定理定理15.415.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通，且是单向连通，且D中恰中恰有两个奇度顶点，其中一个入度比出度大有两个奇度顶点，其中一个入度比出度大1 1，另一个出度比入，另一个出度比入度大度大1 1，而其余顶点入度都等于出度。，而其余顶点入度都等于
7、出度。(举例举例)定理定理15.515.5 G是非平凡欧拉图当且仅当是非平凡欧拉图当且仅当G是连通且为若干个边不重是连通且为若干个边不重圈并。圈并。11/1915.2 15.2 哈密顿图哈密顿图q历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图12/19哈密顿周游世界问题哈密顿周游世界问题q哈密顿圈是图论中著名世界难题之一。哈密顿圈是图论中著名世界难题之一。q“18591859年，英国数学家兼物理学家哈密顿提出以年，英国数学家兼物理学家哈密顿提出以下周游世界问题：用一个正十二面体二十个顶点表下周游世界问题：用一个正十二面体二十个顶点表示二十个城市，怎样才能从一个城市
8、出发，沿着棱示二十个城市，怎样才能从一个城市出发，沿着棱经过每个城市恰好一次，最终返回到出发点？经过每个城市恰好一次，最终返回到出发点？13/19哈密顿图哈密顿图 定义定义15.215.2 经过图（有向图或无向图）中经过图（有向图或无向图）中全部顶点一次且仅一全部顶点一次且仅一次通路次通路称为称为哈密顿通路哈密顿通路。经过图中。经过图中全部顶点一次且仅一次回全部顶点一次且仅一次回路路称为称为哈密顿回路哈密顿回路。含有哈密顿回路图称为。含有哈密顿回路图称为哈密顿图哈密顿图，含有，含有哈密顿通路但不含有哈密顿回路图称为哈密顿通路但不含有哈密顿回路图称为半哈密顿图半哈密顿图。要求：要求：平凡图是哈密
9、顿图。平凡图是哈密顿图。说明说明哈密顿通路是图中生成初级通路，哈密顿通路是图中生成初级通路，哈密顿回路是生成初级回路。哈密顿回路是生成初级回路。判断一个图是否为哈密顿图，就是判断能否将图中全部顶点判断一个图是否为哈密顿图，就是判断能否将图中全部顶点都放置在一个初级回路都放置在一个初级回路(圈圈)上，但这不是一件易事。上，但这不是一件易事。与判断一个图是否为欧拉图不一样，到当前为止，人们还没与判断一个图是否为欧拉图不一样，到当前为止，人们还没有找到哈密顿图简单充分必要条件。有找到哈密顿图简单充分必要条件。14/19例题例题(1)(2)(1)(2)是哈密顿图。是哈密顿图。(3)(3)是半哈密顿图。
10、是半哈密顿图。(4)(4)既不是哈密顿图，也不是半哈密顿图。既不是哈密顿图，也不是半哈密顿图。15/19推论推论 推论推论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|+116/19例例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不是哈密不是哈密顿图，也不是半哈密顿图。顿图，也不是半哈密顿图。17/19例例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不是哈
12、密顿图，不是哈密顿图，但但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是哈密顿图。是哈密顿图。18/19例例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可可知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。知，它不是哈密顿图。但存在哈密顿通路，所以是半哈密顿图。19/19
