离散数学第八章.

第八章一些特殊的图第一节二部图内容：二部图。重点：二部图的定义及判定。本节讨论的图均为无向图。一、二部图的定义。1、若存在无向图的顶点集,GVEV的一个划分，12VVV12VV，，使得G中任何一条边的两个端点分别在1V2V和中，则称G为二部图(或偶图)。其中12,VV称互补顶点子集，G记为12,,GVVE。一、二部图的定义。2、完全二部图(或完全偶图)。若中任一顶点与1V2V中每一顶点均有且只有一条边相关联，则称此二部图G为完全二部图(或完全偶图)。若，则记完全二部图为1Vn，2Vm,nmK。例1、(1)(2)二部图完全二部图2,3K二部图例1、(3)完全二部图3,3K二部图二、判定定理。一个无向图,GVE是二部图当且仅当G中无奇数长度的回路。例2、判断以下是否二部图。abcdefgh(1)二部图图(1)中所有的回路长度均为偶数。(思考，求其互补顶点子集)例2、判断以下是否二部图。(2)二部图(2)例1同构以上二图均为2,3K。例2、判断以下是否二部图。(3)(3)例1同构二部图以上二图均为3,3K。例2、判断以下是否二部图。(4)fedcba不是二部图，因图中存在长为3的回路bcdb。第二节欧拉图内容：欧拉图。重点：1、欧拉图的定义，2、无向图是否具有欧拉通路或回路的判定。了解：有向图是否具有欧拉通路或回路的判定。一、问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题(2)BACD二、定义。欧拉通路(欧拉迹)——通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路(欧拉闭迹)——通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图——存在欧拉回路的图。注意：(1)欧拉通路与欧拉回路不同。(2)欧拉图指具有欧拉回路(并非通路)的图。(3)欧拉通路(回路)必是简单通路(回路)。(4)连通是具有欧拉通路(回路)的必要条件。(5)欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，GGG中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)GG连通，G中均G为偶度顶点。例1、以下图形能否一笔画成？(1)(2)例1、以下图形能否一笔画成？(3)(4)例2、两只蚂蚁比赛问题。G图abc(甲)(乙)两只蚂蚁甲、乙分别处在图中的顶点处，并设图,abG中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点处。如果它们速度相同，问谁最先到达目的地？c四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两个顶点外，其DD余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(DD为欧拉图)连通，DD中所有顶点的入度等于出度。例3、判断以下有向图是否欧拉图。第三节哈密尔顿图内容：哈密尔顿图。重点：哈密尔顿图的定义。一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。(1)(2)二、哈密尔顿图。哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。哈密尔顿图——存在哈密尔顿回路的图。注意：(1)哈密尔顿通路与哈密尔顿回路不同。(2)哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。(3)哈密尔顿通路(回路)必是初级通路(回路)。(4)连通是具有哈密尔顿通路(回路)的必要条件。注意：(5)若图通路。G具有哈密尔顿回路，则必有哈密尔顿(6)阶图的哈密尔顿通路长为n1n，回路长为n。三、判定。采用尝试的办法。例1、判断下图是否具有哈密尔顿回路，通路。(1)解：存在哈密尔顿通路，但不存在哈密尔顿回路。例1、判断下图是否具有哈密尔顿回路，通路。解：是哈密尔顿图，存在哈密尔顿回路和通路。(2)例1、判断下图是否具有哈密尔顿回路，通路。解：不存在哈密尔顿回路，也不存在哈密尔顿通路。(3)例2、画一个无向图，使它(1)具有欧拉回路和哈密尔顿回路，解：(2)具有欧拉回路而没有哈密尔顿回路，解：例2、画一个无向图，使它(3)具有哈密尔顿回路而没有欧拉回路，(4)既没有欧拉回路，也没有哈密尔顿回路。解：解：第四节平面图内容：平面图。重点：1、平面图的概念，2、常见的非平面图5K，，3,3K3、平面图中面的次数与边数关系deg()2iRm4、平面图的欧拉公式2nmr。了解：极大平面图，极小非平面图。本节讨论的图均为无向图。一、平面图的概念。1、定义：一个图如果能以这样的方式画在G平面上：除顶点处外没有边交叉出现，则称G为平面图，画出的没有边交叉出现的图称为G的一个平面嵌入或G的一个平面图。例1、(2)(1)(4)(3)例1、(6)(5)(8)(7)2、极大平面图，极小非平面图。极大平面图——若在平面图G中任意不相邻的两个顶点之间再加一条边，所得图为非平面图，则G为极大平面图。例如：为极大平面图。3K，4K2、极大平面图，极小非平面图。极小非平面图例如：都是极小非平面图。5K，3,3K——若在非平面图G中任意删除一条边后，所得图是平面图，则面图。为极小非平G二、平面图中面、次数与图的顶点、边数等的关系。1、定义：设是一个连通的平面图(指GG某个平面嵌入)，的面——平面图的区域(回路围成的)，无限面(外部面)——面积无限的区域，记0R，有限面(内部面)——面积有限的区域，边界——包围面的边(回路)，二、平面图中面、次数与图的顶点、边数等的关系。1、定义：设是一个连通的平面图(指GG某个平面嵌入)，的次数——面边界的长度，记Rdeg()R。若是非连通的平面图，设GG有(2)kk个连通分支，则的无限面G的边界由0Rk个回路形成。例2、2R1R0R6v5v4v3v2v1v1deg()3R2deg()3R0deg()8R的边界为复杂回路0R123456541vvvvvvvvv。注意：(1)一个平面图的无限面只有一个。(2)同一个平面图可以有不同形状的平面嵌入(互相同构)。(3)不同的平面嵌入可能将某个有限面变成无限面，而将无限面变成有限面。例3、图(2)，(3)都是图(1)的平面嵌入，图(2)中，0deg()3R，图(3)中，0deg()4R，它们虽然形状不同，但都与(1)同构。2R3R1R0R1R2R3R0R4R(1)(2)(3)4R2、平面图中面次数与边数的关系。1deg()2riiRm为面数)(r3、欧拉公式。设为连通的平面图，顶点数为G，边数为nm，面数为，则r2nmr如例3中，(1)图(1)中5n8m，，则25rmn第八章小结与例题一、二部图。1、基本概念。二部图，完全二部图。2、运用。判定一个图是否二部图或完全二部图。二、欧拉图。1、基本概念。欧拉通路，欧拉回路，欧拉图。2、运用。判定无向图是否具有欧拉通路或回路。三、哈密尔顿图。1、基本概念。哈密尔顿通路，哈密尔顿回路，哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。四、平面图。1、基本概念。平面图；平面图的面及次数。2、运用。利用定义判断某些图是否为平面图。例1、画出完全二部图1,4K3,2K2,4K，和。3,2K2,4K1,4K解：例2、完全二部图中，边数为多少？,rsKm解：mrs例3、设完全二部图,rsK，问：(1)当为何值时，为欧拉图。,rs,rsK解：当,rs均为偶数时，为欧拉图。,rsK(2)当为何值时，为哈密尔顿图。,rs,rsK解：当(1)rs时，为哈密尔顿图。,rsK例2、完全二部图中，边数为多少？,rsKm解：mrs例3、设完全二部图,rsK，问：(3)各举出一个完全二部图是平面图和非平面图的例子。解：1,1K，都是平面图，2,2K2,3K3,2K，，3,3K是非平面图。例4、画一个欧拉图，使它具有：(1)偶数个顶点，偶数条边。(2)奇数个顶点，奇数条边。解：解：例4、画一个欧拉图，使它具有：(3)偶数个顶点，奇数条边。(4)奇数个顶点，偶数条边。解：解：例5、今有,,,,,,abcdefg七个人，已知下列事实：会讲英语；会讲英语和汉语；ab会讲英语、意大利语和俄语；c会讲日语和汉语；d会讲德语和意大利语；e会讲法语、日语和俄语；f会讲法语和德语。g试问这七个人应如何排座位，才能使每个人都能和他身边的两个人交谈？解：语言就连一条边，这样得到无向图G，再求G的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同abcdefg图GabcdefgG的哈－回路例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？(1)解：不是欧拉图，不是哈密尔顿图，是平面图，不是二部图。例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？解：是欧拉图，是哈密尔顿图，是平面图，但不是二部图。(2)例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？解：不是欧拉图，是哈密尔顿图，是平面图，不是二部图。(3)例6、下图中哪些是欧拉图，哪些是哈密尔顿图，哪些是平面图，哪些是二部图？解：不是欧拉图，是哈密尔顿图，不是平面图，不是二部图。(4)解：由于的每个顶点的度数均为nK1n，故当为奇数时，为欧拉图。nnK解：要使仅存在欧拉通路，nK中只能有2个nK奇度顶点，而不含偶度顶点(因每个顶点均为度)，故只有1n符合要求。2K为何值时，无向完全图例7、nnK是欧拉图？（1）为何值时，无向完全图n仅存在欧拉通路nK而不存在欧拉回路？（2）例8、已知图如右：G(1)求的平面嵌入。G解：(2)次数最高的面的次数。解：次数最高的为无限面，其次数为10。例8、已知图如右：G(3)次数最低的面的次数。(4)总次数。解：次数最低的为环围成的面，其次数为1。解：总次数deg()221326iRm。