离散数学教学课件：第8章 一些特殊的图

第八章

一些特殊的图

第一节

二部图

内容：二部图。重点：二部图的定义及判定。本节讨论的图均为无向图。一、二部图的定义。1、若存在无向图的顶点集的一个划分，，，使得中任何一条边的两个端点分别在和中，则称为二部图

(或偶图)。其中称互补顶点子集，记为。一、二部图的定义。2、完全二部图

(或完全偶图)。若中任一顶点与中每一顶点均有且只有一条边相关联，则称此二部图为完全二部图

(或完全偶图)。若，则记完全二部图为，。例1、二部图完全二部图二部图例1、完全二部图二部图二、判定定理。一个无向图是二部图当且仅当中无奇数长度的回路。例2、判断以下是否二部图。(1)二部图图(1)中所有的回路长度均为偶数。(思考，求其互补顶点子集)例2、判断以下是否二部图。二部图例1同构以上二图均为。例2、判断以下是否二部图。例1同构二部图以上二图均为。例2、判断以下是否二部图。不是二部图，因图中存在长为3的回路

。第二节

欧拉图内容：欧拉图。重点：1、欧拉图的定义，2、无向图是否具有欧拉通路或回路的判定。了解：有向图是否具有欧拉通路或回路的判定。一、问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题二、定义。欧拉通路

(欧拉迹)——通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路

(欧拉闭迹)——通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图——存在欧拉回路的图。注意：(1)欧拉通路与欧拉回路不同。(2)欧拉图指具有欧拉回路(并非通路)的图。(3)欧拉通路(回路)必是简单通路(回路)。(4)连通是具有欧拉通路(回路)的必要条件。(5)欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)连通，中均为偶度顶点。例1、以下图形能否一笔画成？例1、以下图形能否一笔画成？例2、两只蚂蚁比赛问题。两只蚂蚁甲、乙分别处在图中的顶点处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点处。如果它们速度相同，问谁最先到达目的地？四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(为欧拉图)连通，中所有顶点的入度等于出度。例3、判断以下有向图是否欧拉图。第三节

哈密尔顿图内容：哈密尔顿图。重点：哈密尔顿图的定义。一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。二、哈密尔顿图。哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。哈密尔顿图——存在哈密尔顿回路的图。注意：(1)哈密尔顿通路与哈密尔顿回路不同。(2)哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。(3)哈密尔顿通路(回路)必是初级通路(回路)。

(4)连通是具有哈密尔顿通路(回路)的必要条件。注意：(5)若图通路。具有哈密尔顿回路，则必有哈密尔顿(6)阶图的哈密尔顿通路长为，回路长为。三、判定。采用尝试的办法。例1、判断下图是否具有哈密尔顿回路，通路。解：存在哈密尔顿通路，但不存在哈密尔顿回路。例1、判断下图是否具有哈密尔顿回路，通路。解：是哈密尔顿图，存在哈密尔顿回路和通路。例1、判断下图是否具有哈密尔顿回路，通路。解：不存在哈密尔顿回路，也不存在哈密尔顿通路。例2、画一个无向图，使它(1)具有欧拉回路和哈密尔顿回路，解：(2)具有欧拉回路而没有哈密尔顿回路，解：例2、画一个无向图，使它(3)具有哈密尔顿回路而没有欧拉回路，(4)既没有欧拉回路，也没有哈密尔顿回路。解：解：第四节

平面图内容：平面图。重点：1、平面图的概念，2、常见的非平面图，，3、平面图中面的次数与边数关系4、平面图的欧拉公式。了解：极大平面图，极小非平面图。本节讨论的图均为无向图。一、平面图的概念。1、定义：一个图如果能以这样的方式画在平面上：除顶点处外没有边交叉出现，则称为平面图，画出的没有边交叉出现的图称为的一个平面嵌入或的一个平面图。例1、例1、2、极大平面图，极小非平面图。极大平面图——若在平面图中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则为极大平面图。例如：为极大平面图。，2、极大平面图，极小非平面图。极小非平面图

例如：都是极小非平面图。，——若在非平面图中任意删除一条边后，所得图是平面图，则面图。为极小非平二、平面图中面、次数与图的顶点、边数等的关系。1、定义：设是一个连通的平面图

(指某个平面嵌入)，的面——平面图的区域

(回路围成的)，无限面

(外部面)——面积无限的区域，记，有限面

(内部面)——面积有限的区域，边界——包围面的边

(回路)，二、平面图中面、次数与图的顶点、边数等的关系。1、定义：设是一个连通的平面图

(指某个平面嵌入)，的次数——面边界的长度，记。若是非连通的平面图，设有个连通分支，则的无限面的边界由个回路形成。例2、的边界为复杂回路

。注意：(1)一个平面图的无限面只有一个。(2)同一个平面图可以有不同形状的平面嵌入(互相同构)。(3)不同的平面嵌入可能将某个有限面变成无限面，而将无限面变成有限面。例3、图(2)，(3)都是图(1)的平面嵌入，图(2)中，，图(3)中，，它们虽然形状不同，但都与(1)同构。2、平面图中面次数与边数的关系。为面数)(3、欧拉公式。设为连通的平面图，顶点数为，边数为，面数为，则如例3中，图(1)中，，则第八章

小结与例题一、二部图。1、基本概念。二部图，完全二部图。2、运用。判定一个图是否二部图或完全二部图。二、欧拉图。1、基本概念。欧拉通路，欧拉回路，欧拉图。2、运用。判定无向图是否具有欧拉通路或回路。三、哈密尔顿图。1、基本概念。哈密尔顿通路，哈密尔顿回路，哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。四、平面图。1、基本概念。平面图；平面图的面及次数。2、运用。利用定义判断某些图是否为平面图。例1、画出完全二部图，和。解：例2、完全二部图中，边数为多少？解：例3、设完全二部图，问：(1)当为何值时，为欧拉图。解：当均为偶数时，为欧拉图。(2)当为何值时，为哈密尔顿图。解：当时，为哈密尔顿图。例2、完全二部图中，边数为多少？解：例3、设完全二部图，问：(3)各举出一个完全二部图是平面图和非平面图的例子。解：，都是平面图，，，是非平面图。例4、画一个欧拉图，使它具有：(1)偶数个顶点，偶数条边。(2)奇数个顶点，奇数条边。解：解：例4、画一个欧拉图，使它具有：(3)偶数个顶点，奇数条边。(4)奇数个顶点，偶数条边。解：解：例5、今有七个人，已知下列事实：会讲英语；会讲英语和汉语；会讲英语、意大利语和俄语；会讲日语和汉语；会讲德语和意大利语；会讲法语、日语和俄语；会讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的两个人交谈？解：语言就连一条边，这样得到无向图，再求的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同图的哈－回路例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？(1)解：不是欧拉图，不是哈密尔顿图，是平面图，不是二部图。例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？解：是欧拉图，是哈密尔顿图，是平面图，但不是二部图。(2)例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？解：不是欧拉图，是哈密尔顿图，是平面图，不是二部图。(3)例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？解：不是欧拉图，是哈密尔顿图，不是平面图，不是二部图。(4)解：由于的每个顶点的度数均为，故当为奇数时，为欧拉图。解：要使仅存在欧拉通路，中只能有2个奇度顶点，而不含偶度顶点(因每个顶点均为度)，故只有符合