离散数学第八章

第八章

一些特殊的图

第一节

二部图

内容：二部图。重点：二部图的定义及判定。本节讨论的图均为无向图。一、二部图的定义。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)不同的平面嵌入可能将某个有限面变成无限面，而将无限面变成有限面