离散数学第七章-一些特殊的图课件

1、内容：二部图、欧拉图。重点：二部图、欧拉图的定义及判定。第七章 一些特殊的图 第一节 二部图与欧拉图 一、二部图的定义。1、若存在无向图的顶点集的一个划分，使得中任何一条边的两个端点分别在和中，则称为二部图 (或偶图)。其中称互补顶点子集，记为。2、完全二部图 (或完全偶图)。若中任一顶点与中每一顶点均有且只有一条边相关联，则称此二部图为完全二部图 (或完全偶图)。若，则记完全二部图为，。例1、二部图完全二部图完全二部图二、判定定理。一个无向图是二部图当且仅当中无奇数长度的回路。例2、判断以下是否二部图。(1)二部图图(1)中所有的回路长度均为偶数。(思考，求其互补顶点子集)二部图例1同构以上

2、二图均为。例1同构二部图以上二图均为。不是二部图，因图中存在长为3的回路 。三、欧拉图问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题四、欧拉图定义。欧拉通路 (欧拉迹)通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路 (欧拉闭迹)通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图存在欧拉回路的图。注意：(1) 欧拉通路与欧拉回路不同。(2) 欧拉图指具有欧拉回路(并非通路)的图。(3) 欧拉通路(回路)必是简单通路(回路)。(4) 连通是具有欧拉通路(回路)的必要条件。(5) 欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。三、无向图是否具有欧拉通

3、路或回路的判定。有欧拉通路连通，中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)连通，中均为偶度顶点。例3、以下图形能否一笔画成？四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(为欧拉图)连通，中所有顶点的入度等于出度。例4、判断以下有向图是否欧拉图。内容：哈密尔顿图、平面图。重点：1、哈密尔顿图的定义。第二节 哈密尔顿图与平面图2、平面图的概念，3、常见的非平面图，4、平面图中面的次数与边数关系5、平面图的欧拉公式。了解：1、哈密尔顿

4、图的充分条件2、极大平面图，极小非平面图。一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。二、哈密尔顿图。哈密尔顿通路通过图中每个顶点一次且仅一次的通路。哈密尔顿回路通过图中每个顶点一次且仅一次的回路。哈密尔顿图存在哈密尔顿回路的图。注意：(1) 哈密尔顿通路与哈密尔顿回路不同。(2) 哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。(3) 哈密尔顿通路(回路)必是初级通路(回路)。 (4) 连通是具有哈密尔顿通路(回路)的必要条件。(5) 若图具有哈密尔顿回路，则必有哈密尔顿通路。(6) 阶图的哈密尔顿通路长为，回路长为。例1、判断下图是否具有哈密尔顿回路，通路。解：存在哈密尔

5、顿通路，但不存在哈密尔顿回路。三、判定。采用尝试的办法。 解：是哈密尔顿图，存在哈密尔顿回路和通路。解：不存在哈密尔顿回路，也不存在哈密尔顿通路。例2、画一个无向图，使它(1) 具有欧拉回路和哈密尔顿回路，解：(2) 具有欧拉回路而没有哈密尔顿回路，解：(3) 具有哈密尔顿回路而没有欧拉回路，(4) 既没有欧拉回路，也没有哈密尔顿回路。解：解：下面讨论的图均为无向图。四、平面图的概念。1、定义：一个图如果能以这样的方式画在平面上：除顶点处外没有边交叉出现，则称为平面图，画出的没有边交叉出现的图称为的一个平面嵌入或的一个平面图。例3、2、极大平面图，极小非平面图。极大平面图若在平面图中任意不相邻

6、的两个顶点之间再加一条边，所得图为非平面图，则为极大平面图。例如：为极大平面图。，极小非平面图 若在非平面图中任意删除一条边后，所得图是平面图，则面图。为极小非平例如：都是极小非平面图。，五、平面图中面、次数与图的顶点、边数等的关系。1、定义：设是一个连通的平面图 (指的某个平面嵌入)，面平面图的区域 (回路围成的)，无限面 (外部面)面积无限的区域，记，有限面 (内部面)面积有限的区域，边界包围面的边 (回路)，次数面边界的长度，记。若是非连通的平面图，设有个连通分支，则的无限面的边界由个回路形成。例4、的边界为复杂回路 。注意：(1) 一个平面图的无限面只有一个。(2) 同一个平面图可以有

7、不同形状的平面嵌入(互相同构)。(3) 不同的平面嵌入可能将某个有限面变成无限面，而将无限面变成有限面。例5、图(2)，(3)都是图(1)的平面嵌入，图(2)中，图(3)中，它们虽然形状不同，但都与(1)同构。2、平面图中面次数与边数的关系。为面数)(3、欧拉公式。设为连通的平面图，顶点数为，边数为，面数为，则第三节无向树内容：无向树重点：无向树的概念最小生成树的概念了解：避圈法求最小生成树一、无向树的定义1、连通而不含回路的无向图称为无向树，简称树，常用表示树 2、连通分支数大于等于2，且每个连通分支均是树的非连通无向图称为森林平凡图称为平凡树二、生成树的定义1、设是无向连通图， 是的生成子

8、图，并且是树，则称 是的生成树 2、在中的边称为 的树枝， 不在 中的边称为 的弦 设无向连通带权图 的所有弦的集合的导出子图称为 的余树 三、最小生成树的定义1、是 ，的一棵生成树 各边带权之和称为 的权，记作 。 带权最小的生成树称为最小生成树 的所有生成树中2、克鲁斯克尔 法，又称“避圈法”，求 最小生成树第四节 根树及其应用内容：根树，树根，树叶，树高，家族树，有序树，最优元树，Huffman算法 ,前缀码重点：根树的基本概念，最优元树，Huffman算法 了解：2元树的3种周游方式 一、根树的定义1、一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根

9、树 入度为0的顶点称为树根；入度为1、出度大于0的顶点称为内点， 内点和树根统称为分支点 入度为1、出度为0的顶点称为树叶； 在根树中，从树根到任意顶点的通路长度称为的层数，记为 称层数相同的顶点在同一层上层数最大的顶点的层数称为树高，记为 2、一棵根树也常称为一棵家族树： 若顶点邻接到顶点，则称 为的儿子，为的父亲； 若同为的儿子，则称为兄弟； 若，而可达，则称为的祖先，的后代 为 3、如果将根树每一层上的顶点都规定次序，这样的根树称为有序树在编码理论和计算机程序等问题中，常常要考虑同一层上的顶点的顺序，因而需要有序树的概念二、最优2元树 1、设2元树有片树叶，分别带权为 （为实数，），称

10、为 的权，其中 为带权 的树叶 的层数在所有的带权 中，带权最小的2元树称为最优2元树的2元树算法： 2、给定实数，且 （1）连接为权的两片树叶，得一分支点，其权为；（2）在 ，中选出两个最小的权，连接它们对应的顶点（不一定都是树叶），得分支点及所带的权；（3）重复（2），直到形成个分支点，片树叶为止3、设为长度是的符号串，称其子串分别为的长度为的前缀设为一个符号串集合，若对于任意的与互不为前缀，则称为前缀码 三、2元树的三种周游方式 对于一棵根树的每个顶点都访问一次且仅一次称为可行遍或周游一棵树对于2元有序正则树主要有以下3种行遍方法（1）中序行遍法 其访问次序为：左子树，树根，右子树（2）

11、前序行遍法 其访问次序为：树根，左子树，右子树（3）后序行遍法 其访问次序为：左子树，右子树，树根一、二部图与欧拉图。1、基本概念。二部图，完全二部图，欧拉通路，欧拉回路，欧拉图。2、运用。判定一个图是否是二部图或完全二部图。第七章 小结与例题判定无向图是否具有欧拉通路或回路。二、哈密尔顿图与平面图。1、基本概念。哈密尔顿通路，哈密尔顿回路，哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。平面图；平面图的面及次数。利用定义判断某些图是否为平面图。三、无向树与根树1、基本概念。无向树，最小生成树，根树，最优2元树2、运用。Huffman算法求最优元树避圈法求最小生成树例1、画出完全二

12、部图，和。解：例2、完全二部图中，边数为多少？解：例3、设完全二部图，问：(1) 当为何值时，为欧拉图。解：当均为偶数时，为欧拉图。(2) 当为何值时，为哈密尔顿图。解：当时，为哈密尔顿图。(3) 各举出一个完全二部图是平面图和非平面图的例子。解：，都是平面图，是非平面图。例4、画一个欧拉图，使它具有：(1) 偶数个顶点，偶数条边。(2) 奇数个顶点，奇数条边。解：解：(3) 偶数个顶点，奇数条边。(4) 奇数个顶点，偶数条边。解：解：例5、今有七个人，已知下列事实：会讲英语；会讲英语和汉语；会讲英语、意大利语和俄语；会讲日语和汉语；会讲德语和意大利语；会讲法语、日语和俄语；会讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的两个人交谈？解：语言就连一条边，这样得到无向图，再求的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同图的哈回路例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？(1)解：不是欧拉图，不是哈