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

1、内容：内容：二部图、欧拉图。重点：重点：二部图、欧拉图的定义及判定。第七章第七章 一些特殊的图一些特殊的图 第一节第一节 二部图与欧拉图二部图与欧拉图 一、二部图的定义。一、二部图的定义。1、若存在无向图的顶点集,GV EV的一个划分，12VVV12VV，使得G中任何一条边的两个端点分别在1V2V和中，则称G为二部图二部图(或偶图偶图)。其中12,V V称互补顶点子集，G记为12,GV V E。2、完全二部图(或完全偶图)。若中任一顶点与1V2V中每一顶点均有且只有一条边相关联，则称此二部图G为完全二部完全二部图图(或完全偶图完全偶图)。若，则记完全二部图为1Vn，2Vm,n mK。例例1、(

2、1)(2)二部图完全二部图2,3K(3)完全二部图3,3K二、判定定理。二、判定定理。一个无向图,GV E是二部图当且仅当G中无奇数长度的回路。例例2、判断以下是否二部图。abcdefgh(1)二部图图(1)中所有的回路长度均为偶数。(思考，求其互补顶点子集)(2)二部图(2)例1同构以上二图均为2,3K。(3)(3)例1同构二部图以上二图均为3,3K。(4)fedcba不是二部图，因图中存在长为3的回路 bcdb。三、欧拉图问题的提出。三、欧拉图问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题(2)BACD四、欧拉图定义。欧拉通路欧拉通路(欧拉迹欧拉迹)通过图中每条边一次且仅一次，并

3、且过每一顶点的通路。欧拉回路欧拉回路(欧拉闭迹欧拉闭迹)通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图欧拉图 存在欧拉回路的图。注意：注意：(1)欧拉通路与欧拉回路不同。(2)欧拉图指具有欧拉回路(并非通路)的图。(3)欧拉通路(回路)必是简单通路(回路)。(4)连通是具有欧拉通路(回路)的必要条件。(5)欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。三、无向图是否具有欧拉通路或回路的判定。三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，G GG中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)GG连通，G中均G为偶度顶点。例例3

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

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

6、通路长为n1n，回路长为n。例例1、判断下图是否具有哈密尔顿回路，通路。(1)解：解：存在哈密尔顿通路，但不存在哈密尔顿回路。三、判定。三、判定。采用尝试的办法。解：解：是哈密尔顿图，存在哈密尔顿回路和通路。(2)(3)解：解：不存在哈密尔顿回路，也不存在哈密尔顿通路。例例2、画一个无向图，使它(1)具有欧拉回路和哈密尔顿回路，解：解：(2)具有欧拉回路而没有哈密尔顿回路，解：解：(3)具有哈密尔顿回路而没有欧拉回路，(4)既没有欧拉回路，也没有哈密尔顿回路。解：解：解：解：下面讨论的图均为无向图。四、平面图的概念。四、平面图的概念。1、定义定义：一个图如果能以这样的方式画在G平面上：除顶点处

7、外没有边交叉出现，则称G为平面图平面图，画出的没有边交叉出现的图称为G的一个平面嵌入平面嵌入或G的一个平面图平面图。例例3、(2)(1)(4)(3)(6)(5)(8)(7)2、极大平面图，极小非平面图。极大平面图极大平面图 若在平面图G中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则G为极大平面图。例如：为极大平面图。3K，4K极小非平面图极小非平面图 若在非平面图G中任意删除一条边后，所得图是平面图，则面图。为极小非平G例如：都是极小非平面图。5K，3,3K五、平面图中面、次数与图的顶点、边数等五、平面图中面、次数与图的顶点、边数等的关系。的关系。1、定义：定义：设是一个连通的平面

8、图(指GG的某个平面嵌入)，面面平面图的区域(回路围成的)，无限面无限面(外部面外部面)面积无限的区域，记0R，有限面有限面(内部面内部面)面积有限的区域，边界边界包围面的边(回路)，次数次数面边界的长度，记Rdeg()R。若是非连通的平面图，设GG有(2)k k 个连通分支，则的无限面G的边界由0Rk个回路形成。例例4、2R1R0R6v5v4v3v2v1v1deg()3R2deg()3R0deg()8R的边界为复杂回路 0R1 2 3 4 5 6 5 4 1v v v v v v v v v。注意：注意：(1)一个平面图的无限面只有一个。(2)同一个平面图可以有不同形状的平面嵌入(互相同构)

9、。(3)不同的平面嵌入可能将某个有限面变成无限面，而将无限面变成有限面。例例5、图(2)，(3)都是图(1)的平面嵌入，图(2)中，0deg()3R，图(3)中，0deg()4R，它们虽然形状不同，但都与(1)同构。2R3R1R0R1R2R3R0R4R(1)(2)(3)4R2、平面图中面次数与边数的关系。1deg()2riiRm为面数)(r3、欧拉公式。设为连通的平面图，顶点数为G，边数为nm，面数为，则r2nmr第三节无向树内容：无向树重点：无向树的概念最小生成树的概念了解：避圈法求最小生成树一、无向树的定义1、连通而不含回路的无向图称为无向树无向树，简称树树，常用T表示树 2、连通分支数大

10、于等于2，且每个连通分支均是树的非连通无向图称为森林森林平凡图称为平凡树平凡树二、生成树生成树的定义1、设EVG,是无向连通图，T是G的生成子图，并且T是树，则称 T是G的生成树生成树 G2、在T中的边称为 T的树枝，G不在 T中的边称为 T的弦 设无向连通带权图 的所有弦的集合的导出子图称为 TT的余树余树 三、最小生成树的定义1、是 WEVG,，TG的一棵生成树 T各边带权之和称为 T的权，记作 。)(TWG带权最小的生成树称为最小生成树最小生成树 的所有生成树中2、克鲁斯克尔)(Kruskal法，又称“避圈法避圈法”，求 最小生成树第四节第四节 根树及其应用根树及其应用内容：根树，树根，

11、树叶，树高，家族树，有序树，最优元树，Huffman算法,前缀码重点：根树的基本概念，最优元树，Huffman算法 了解：2元树的3种周游方式 一、根树的定义1、一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树根树 入度为0的顶点称为树根树根；入度为1、出度大于0的顶点称为内点内点，内点和树根统称为分支点分支点 入度为1、出度为0的顶点称为树叶树叶；vv在根树中，从树根到任意顶点的通路长度称为的层数层数，记为)(vl称层数相同的顶点在同一层上层数最大的顶点的层数称为树高，树高，记为)(Th2、一棵根树也常称为一棵家族树家族树：ab若顶点 邻接到顶点，则称

12、baab为的儿子儿子，为的父亲父亲；cb,acb,若同为的儿子，则称为兄弟兄弟；da adadd若，而可达，则称为的祖先祖先，的后代后代 为a 3、如果将根树每一层上的顶点都规定次序，这样的根树称为有序树在编码理论和计算机程序等问题中，常常要考虑同一层上的顶点的顺序，因而需要有序树的概念二、最优二、最优2元树元树Tt 1、设2元树有 片树叶，分别带权为 ti,21iti,2,1（为实数，），称)(TW)(1itiiL为 T的权，其中)(iL为带权 i的树叶 iv的层数在所有的带权 t,21中，带权最小的2元树称为最优最优2元树元树的2元树Huffman算法：2、t,21t21给定实数，且 21

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

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

15、，最优2元树2、运用。Huffman算法求最优元树避圈法求最小生成树例例1、画出完全二部图1,4K3,2K2,4K，和。3,2K2,4K1,4K解：解：例例2、完全二部图中，边数为多少？,r sKm解：解：mrs例例3、设完全二部图,r sK，问：(1)当为何值时，为欧拉图。,r s,r sK解：解：当,r s均为偶数时，为欧拉图。,r sK(2)当为何值时，为哈密尔顿图。,r s,r sK解：解：当(1)rs时，为哈密尔顿图。,r sK(3)各举出一个完全二部图是平面图和非平面图的例子。解：解：1,1K，都是平面图，2,2K2,3K3,2K，3,3K是非平面图。例例4、画一个欧拉图，使它具有

16、：(1)偶数个顶点，偶数条边。(2)奇数个顶点，奇数条边。解：解：解：解：(3)偶数个顶点，奇数条边。(4)奇数个顶点，偶数条边。解：解：解：解：例例5、今有,a b c d e f g七个人，已知下列事实：会讲英语；会讲英语和汉语；ab会讲英语、意大利语和俄语；c会讲日语和汉语；d会讲德语和意大利语；e会讲法语、日语和俄语；f会讲法语和德语。g试问这七个人应如何排座位，才能使每个人都能和他身边的两个人交谈？解：解：语言就连一条边，这样得到无向图G，再求G的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同abcdefg图GabcdefgG的哈回路例例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？(1)解：解：不是欧拉图，不是哈密尔顿图，是平面图，不是二部图。解：解：是欧拉图，是哈密尔顿图，是平面图，但不是二部图。(2)(3)解：不解：不是欧拉图，是哈密尔顿图，解：不解：不是欧拉图，是哈密尔顿图，不是平面图，不是二部图。(4)例例、已知图 如右：G(1)求的平面嵌入。G解：解：(2)次数最高的面的次数。解：解：次数最高的为无限面，其次数为10。(3)次数最低的面的次数。(4)总次数。解：解：次数最低的为环围成的面，其次数为1。解：解：总次数deg()22 1326iRm。