北大离散数学chap8名师优质课获奖市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,第八章,一些特殊图,第一节,二部图,第1页,内容：,二部图。,重点：,二部图定义及判定。,本节讨论图均为无向图。,第2页,一、二部图定义。,1,、若存在无向图,顶点集,一个,划分，,，,，使得,中任何,一条边两个端点分别在,和,中，则称,为,二部图,(,或,偶图,),。,其中,称互补顶点子集，,记为,。,第3页,一、二部图定义。,2,、完全二部图,(,或完全偶图,),。,若,中任一顶点与,中每一顶点都有且只有,一条边相关联，则称此二部图为,完全二部,图,(,或,完全偶图,),。,若,，则记完全二部图为,，,。,第4页,例,1,、,二部图,完全二部图,二部图,第5页,例,1,、,完全二部图,二部图,第6页,二、判定定理。,一个无向图,是二部图当且仅当,中无奇数长度回路。,第7页,例,2,、,判断以下是否二部图。,(1),二部图,图,(1),中全部回路长度均为偶数。,(,思索，求其互补顶点子集,),第8页,例,2,、,判断以下是否二部图。,二部图,例,1,同构,以上二图均为,。,第9页,例,2,、,判断以下是否二部图。,例,1,同构,二部图,以上二图均为,。,第10页,例,2,、,判断以下是否二部图。,不是二部图，因图中存在长为,3,回路,。,第11页,第二节,欧拉图,第12页,内容：,欧拉图。,重点：,1,、欧拉图定义，,2,、无向图是否含有欧拉通路或回路,判定。,了解：,有向图是否含有欧拉通路或回路判定。,第13页,一、问题提出。,1736,年，瑞士数学家欧拉，哥尼斯堡七桥问题,第14页,二、定义。,欧拉通路,(,欧拉迹,),经过图中每条边一次,且仅一次，而且过每一顶点通路。,欧拉回路,(,欧拉闭迹,),经过图中每条边一次,且仅一次，而且过每一顶点回路。,欧拉图,存在欧拉回路图。,第15页,注意：,(1),欧拉通路与欧拉回路不一样。,(2),欧拉图指含有欧拉回路,(,并非通路,),图。,(3),欧拉通路,(,回路,),必是简单通路,(,回路,),。,(4),连通是含有欧拉通路,(,回路,),必要条件。,(5),欧拉通路,(,回路,),是经过图中全部边通路,(,回路,),中最短通路,(,回路,),。,第16页,三、无向图是否含有欧拉通路或回路判定。,有欧拉通路,连通，,中只有两个奇度,顶点,(,它们分别是欧拉通路,两个端点,),。,有欧拉回路,(,为欧拉图,),连通，,中均,为偶度顶点。,第17页,例,1,、,以下列图形能否一笔画成？,第18页,例,1,、,以下列图形能否一笔画成？,第19页,例,2,、,两只蚂蚁比赛问题。,两只蚂蚁甲、乙分别处于图,中顶点,处，并设图,中各边长度相等。甲提出同,乙比赛从它们所在顶点出,发，走过图中全部边最终到,达顶点,处。假如它们速度相同，问谁最先,抵达目标地？,第20页,四、有向图是否含有欧拉通路或回路判定。,有欧拉通路,连通，除两个顶点外，其,余顶点入度均等于出度，,这两个特殊顶点中，一个,顶点入度比出度大,1,，另一,个顶点入度比出度小,1,。,有欧拉回路,(,为欧拉图,),连通，,中全部,顶点入度等于出度。,第21页,例,3,、,判断以下有向图是否欧拉图。,第22页,第三节,哈密尔顿图,第23页,内容：,哈密尔顿图。,重点：,哈密尔顿图定义。,第24页,一、问题提出。,1859,年，英国数学家哈密尔顿，周游世界游戏。,第25页,二、哈密尔顿图。,哈密尔顿通路,经过图中每个顶点一次且仅,一次通路。,哈密尔顿回路,经过图中每个顶点一次且仅,一次回路。,哈密尔顿图,存在哈密尔顿回路图。,第26页,注意：,(1),哈密尔顿通路与哈密尔顿回路不一样。,(2),哈密尔顿图是指含有哈密尔顿回路,(,并非通路,),图。,(3),哈密尔顿通路,(,回路,),必是初级通路,(,回路,),。,(4),连通是含有哈密尔顿通路,(,回路,),必要条件。,第27页,注意：,(5),若图,通路。,含有哈密尔顿回路，则必有哈密尔顿,(6),阶图哈密尔顿通路长为,，回路长为,。,三、判定。,采取尝试方法。,第28页,例,1,、,判断下列图是否含有哈密尔顿回路，通路。,解：,存在哈密尔顿通路，,但不存在哈密尔顿回路。,第29页,例,1,、,判断下列图是否含有哈密尔顿回路，通路。,解：,是哈密尔顿图，,存在哈密尔顿回路和通路。,第30页,例,1,、,判断下列图是否含有哈密尔顿回路，通路。,解：,不存在哈密尔顿回路，,也不存在哈密尔顿通路。,第31页,例,2,、,画一个无向图，使它,(1),含有欧拉回路和哈密尔顿回路，,解：,(2),含有欧拉回路而没有哈密尔顿回路，,解：,第32页,例,2,、,画一个无向图，使它,(3),含有哈密尔顿回路而没有欧拉回路，,(4),既没有欧拉回路，也没有哈密尔顿回路。,解：,解：,第33页,第四节,平面图,第34页,内容：,平面图重点：,1,、平面图概念，,2,、常见非平面图,，,，,3,、平面图中面次数与边数关系,4,、平面图欧拉公式,。,了解：,极大平面图，极小非平面图。,第35页,本节讨论图均为无向图。,一、平面图概念。,1,、,定义,：,一个图,假如能以这么方式画在,平面上：除顶点处外没有边交叉出现，则称,为,平面图,，画出没有边交叉出现图称为,一个,平面嵌入,或,一个,平面图,。,第36页,例,1,、,第37页,例,1,、,第38页,2,、极大平面图，极小非平面图。,极大平面图,若在平面图,中任意不相邻,两个顶点之间再加一条边，所得图为非平面,图，则,为极大平面图。,比如：,为极大平面图。,，,第39页,2,、极大平面图，极小非平面图。,极小非平面图,比如：,都是极小非平面图。,，,若在非平面图,中任意删除,一条边后，所得图是平面图，则,面图。,为极小非平,第40页,二、平面图中面、次数与图顶点、边数等,关系。,1,、,定义：,设,是一个连通平面图,(,指,某个平面嵌入,),，,面,平面图区域,(,回路围成,),，,无限面,(,外部面,),面积无限区域，记,，,有限面,(,内部面,),面积有限区域，,边界,包围面边,(,回路,),，,第41页,二、平面图中面、次数与图顶点、边数等,关系。,1,、,定义：,设,是一个连通平面图,(,指,某个平面嵌入,),，,次数,面,边界长度，记,。,若,是非连通平面图，设,有,个,连通分支，则,无限面,边界由,个回,路形成。,第42页,例,2,、,边界为复杂回路,。,第43页,注意：,(1),一个平面图无限面只有一个。,(2),同一个平面图能够有不一样形状平面嵌入,(,相互同构,),。,(3),不一样平面嵌入可能将某个有限面变成,无限面，而将无限面变成有限面。,第44页,例,3,、,图,(2),，,(3),都是图,(1),平面嵌入，,图,(2),中，,，,图,(3),中，,，,它们即使形状不一样，但都与,(1),同构。,第45页,2,、平面图中面次数与边数关系。,为面数,),(,3,、欧拉公式。,设,为连通平面图，顶点数为,，边数为,，,面数为,，则,第46页,如例,3,中，,图,(1),中,，,，,则,第47页,第八章,小结与例题,第48页,一、二部图。,1,、基本概念。,二部图，完全二部图。,2,、利用。,判定一个图是否二部图或完全二部图。,第49页,二、欧拉图。,1,、基本概念。,欧拉通路，欧拉回路，欧拉图。,2,、利用。,判定无向图是否含有欧拉通路或回路。,第50页,三、哈密尔顿图。,1,、基本概念。,哈密尔顿通路，哈密尔顿回路，哈密尔顿图。,2,、利用。,判断无向图是否含有哈密尔顿通路或回路。,第51页,四、平面图。,1,、基本概念。,平面图；平面图面及次数。,2,、利用。,利用定义判断一些图是否为平面图。,第52页,例,1,画出完全二部图,，,和,。,解：,第53页,例,2,、,完全二部图,中，边数,为多少？,解：,例,3,、,设完全二部图,，问：,(1),当,为何值时，,为欧拉图。,解：,当,均为偶数时，,为欧拉图。,(2),当,为何值时，,为哈密尔顿图。,解：,当,时，,为哈密尔顿图。,第54页,例,2,、,完全二部图,中，边数,为多少？,解：,例,3,、,设完全二部图,，问：,(3),各举出一个完全二部图是平面图和非平面图,例子。,解：,，,都是平面图，,，,，,是非平面图。,第55页,例,4,、,画一个欧拉图，使它含有：,(1),偶数个顶点，偶数条边。,(2),奇数个顶点，奇数条边。,解：,解：,第56页,例,4,、,画一个欧拉图，使它含有：,(3),偶数个顶点，奇数条边。,(4),奇数个顶点，偶数条边。,解：,解：,第57页,例,5,、,今有,七个人，已知以下事实：,会讲英语；,会讲英语和汉语；,会讲英语、意大利语和俄语；,会讲日语和汉语；,会讲德语和意大利语；,会讲法语、日语和俄语；,会讲法语和德语。,试问这七个人应怎样排座位，才能使每个人,都能和他身边两个人交谈？,第58页,解：,语言就连一条边，这么得到无向图,，再求,哈密尔顿回路。,用七个顶点表示七个人，若两人之间有共同,图,哈回路,第59页,例,6,、,下列图中哪些是欧拉图，哪些是哈密尔顿图，,哪些是平面图，哪些是二部图？,(1),解：,不是欧拉图，,不是哈密尔顿图，,是平面图，,不是二部图。,第60页,例,6,、,下列图中哪些是欧拉图，哪些是哈密尔顿图，,哪些是平面图，哪些是二部图？,解：,是欧拉图，,是哈密尔顿图，,是平面图，,但不是二部图。,(2),第61页,例,6,、,下列图中哪些是欧拉图，哪些是哈密尔顿图，,哪些是平面图，哪些是二部图？,解：不,是欧拉图，,是哈密尔顿图，,是平面图，,不是二部图。,(3),第62页,例,6,、,下列图中哪些是欧拉图，哪些是哈密尔顿图，,哪些是平面图，哪些是二部图？,解：不,是欧拉图，,是哈密尔顿图，,不是平面图，,不是二部图。,(4),第63页,解：,因为,每个顶点度数均为,，,故当,为奇数时，,为欧拉图。,解：,要使,仅存在欧拉通路，,中只能有,2,个,奇度顶点，而不含偶度顶点,(,因每个顶点均为,度,),，故只有,符合要求。,为何值时，无向完全图,例,7,、,是欧拉图？,（,1,）,为何值时，无向完全图,仅存在欧拉通路,而不存在欧拉回路？,（,2,）,第64页,例,8,、,已知图,如右：,(1),求,平面嵌入。,解：,(2),次数最高面次数。,解：,次数最高为无限面，其次数为,10,。,第65页,例,8,、,已知图,如右：,(3),次数最低面次数。,(4),总次数。,解：,次数最低为环围,成面，其次数为,1,。,解：,总次数,。,第66页,