离散数学第8章.ppt

1、第八章 一些特殊的图,第一节 二部图,内容：二部图。,重点：二部图的定义及判定。,本节讨论的图均为无向图。,一、二部图的定义。,一、二部图的定义。,2、完全二部图 (或完全偶图)。,例1、,二部图,完全二部图,二部图,例1、,完全二部图,二部图,二、判定定理。,例2、判断以下是否二部图。,(1),二部图,图(1)中所有的回路长度均为偶数。,(思考，求其互补顶点子集),例2、判断以下是否二部图。,二部图,例2、判断以下是否二部图。,二部图,例2、判断以下是否二部图。,第二节 欧拉图,内容：欧拉图。,重点：1、欧拉图的定义，,了解：有向图是否具有欧拉通路或回路的判定。,一、问题的提出。,1736年

2、，瑞士数学家欧拉，哥尼斯堡七桥问题,二、定义。,欧拉通路 (欧拉迹),欧拉回路 (欧拉闭迹),欧拉图,存在欧拉回路的图。,注意：,(1) 欧拉通路与欧拉回路不同。,(2) 欧拉图指具有欧拉回路(并非通路)的图。,(3) 欧拉通路(回路)必是简单通路(回路)。,(4) 连通是具有欧拉通路(回路)的必要条件。,三、无向图是否具有欧拉通路或回路的判定。,例1、以下图形能否一笔画成？,例1、以下图形能否一笔画成？,例2、两只蚂蚁比赛问题。,四、有向图是否具有欧拉通路或回路的判定。,例3、判断以下有向图是否欧拉图。,第三节 哈密尔顿图,内容：哈密尔顿图。,重点：哈密尔顿图的定义。,一、问题的提出。,18

3、59年，英国数学家哈密尔顿，周游世界游戏。,二、哈密尔顿图。,哈密尔顿通路,哈密尔顿回路,哈密尔顿图,存在哈密尔顿回路的图。,注意：,(1) 哈密尔顿通路与哈密尔顿回路不同。,(3) 哈密尔顿通路(回路)必是初级通路(回路)。,(4) 连通是具有哈密尔顿通路(回路)的必要条件。,注意：,三、判定。,采用尝试的办法。,例1、判断下图是否具有哈密尔顿回路，通路。,例1、判断下图是否具有哈密尔顿回路，通路。,例1、判断下图是否具有哈密尔顿回路，通路。,例2、画一个无向图，使它,(1) 具有欧拉回路和哈密尔顿回路，,解：,(2) 具有欧拉回路而没有哈密尔顿回路，,解：,例2、画一个无向图，使它,(3)

4、 具有哈密尔顿回路而没有欧拉回路，,(4) 既没有欧拉回路，也没有哈密尔顿回路。,解：,解：,第四节 平面图,内容：平面图。,重点：1、平面图的概念，,3、平面图中面的次数与边数关系,了解：极大平面图，极小非平面图。,本节讨论的图均为无向图。,一、平面图的概念。,1、定义：,例1、,例1、,2、极大平面图，极小非平面图。,2、极大平面图，极小非平面图。,极小非平面图,面,平面图的区域 (回路围成的)，,无限面 (外部面),有限面 (内部面),面积有限的区域，,边界,包围面的边 (回路)，,次数,例2、,注意：,(1) 一个平面图的无限面只有一个。,例3、,图(2)，(3)都是图(1)的平面嵌入

5、，,它们虽然形状不同，但都与(1)同构。,2、平面图中面次数与边数的关系。,3、欧拉公式。,如例3中，,则,第八章 小结与例题,一、二部图。,1、基本概念。,二部图，完全二部图。,2、运用。,判定一个图是否二部图或完全二部图。,二、欧拉图。,1、基本概念。,欧拉通路，欧拉回路，欧拉图。,2、运用。,判定无向图是否具有欧拉通路或回路。,三、哈密尔顿图。,1、基本概念。,哈密尔顿通路，哈密尔顿回路，哈密尔顿图。,2、运用。,判断无向图是否具有哈密尔顿通路或回路。,四、平面图。,1、基本概念。,平面图；平面图的面及次数。,2、运用。,利用定义判断某些图是否为平面图。,解：,解：,解：,是非平面图。,例4、画一个欧拉图，使它具有：,(1) 偶数个顶点，偶数条边。,(2) 奇数个顶点，奇数条边。,解：,解：,例4、画一个欧拉图，使它具有：,(3) 偶数个顶点，奇数条边。,(4) 奇数个顶点，偶数条边。,解：,解：,解：,图,的哈回路,(1),解：不是欧拉图，,不是哈密尔顿图，,是平面图，,不是二部图。,解：是欧拉图，,是哈密尔顿图，,是平面图，,但不是二部图。,(2),解：不是欧拉图，,是哈密尔顿图，,是平面图，,不是二部图。,(3),例6、下图中哪些是欧拉图，哪些是哈密尔顿图，,哪些是平面图，哪些是二部图？,解：不是欧拉