离散数学--6.4几种特殊的图省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,6.4,几个特殊图,6.4.1 二部图,二部图充要条件,6.4.2 欧拉图,欧拉回路(通路)及其存在充要条件,6.4.3 哈密顿图,哈密顿回路(通路)及其存在必要条件和充分条件,6.4.4 平面图,1/19,1,二部图,定义6.19,设无向图,G,=,若能将,V,分成,V,1,和,V,2,使得,V,1,V,2,=,V,V,1,V,2,=,且,G,中每条边两个端点都一个,属于,V,1,另一个属于,V,2,则称,G,为,二部图,记为,称,V,1,和,V,2,为,互补顶点子集,.又若,G,是简单图,且,V,1,中每个顶,点均与,V,2,中每个顶点都相邻,则称,G,为,完全二部图,记为,K,r,s,其中,r,=|,V,1,|,s,=|,V,2,|.,K,23,K,33,2/19,2,二部图判别定理,定理6.7,无向图,G,=,是二部图当且仅当,G,中无奇长度,回路,证 必要性.设,G=,是二部图,每条边只能从,V,1,到,V,2,或从,V,2,到,V,1,故任何回路必为偶长度.,充分性.不妨设,G,最少有一条边且连通.取任一顶点,u,令,V,1,=,v,|,v,V,d,(,v,u,),为偶数,V,2,=,v,|,v,V,d,(,v,u,),为奇数,则,V,1,V,2,=,V,V,1,V,2,=,.,先证,V,1,中任意两点不相邻.假设存,在,s,t,V,1,e,=(,s,t,),E,.,设,1,2,分别是,u,到,s,t,短程线,则,1,e,2,是一条回路,其长度为奇数,与假设矛盾.同理可,证,V,2,中任意两点不相邻.,3/19,3,实例,非二部图,非二部图,4/19,4,实例,例1,某中学有3个课外活动小组:数学组,计算机组和生物,组.有赵,钱,孙,李,周5名学生,问分别在下述3种情况下,能,否选出3人各任一个组组长?,(1)赵,钱为数学组组员,赵,孙,李为计算机组组员,孙,李,周为生物组组员.,(2)赵为数学组组员,钱,孙,李为计算机组组员,钱,孙,李,周,为生物组组员.,(3)赵为数学组和计算机组组员,钱,孙,李,周为生物组组员.,5/19,5,实例(续),解,(1),(2)有各种方案,(3)不可能,(1),数,计,生,赵,钱,孙,李,周,(2),数,计,生,赵,钱,孙,李,周,(3),数,计,生,赵,钱,孙,李,周,6/19,6,欧拉图,哥尼斯堡七桥,7/19,7,欧拉图,欧拉通路,:经过全部边且每条边恰好经过一次通路,欧拉回路,:经过全部边且每条边恰好经过一次回路,欧拉图,:有欧拉回路图,说明：,上述定义对无向图和有向图都适用,要求平凡图为欧拉图,欧拉通路是简单通路,欧拉回路是简单回路,环不影响图欧拉性,8/19,8,欧拉图判别定理,定理6.8,无向图,G,含有欧拉回路当且仅当,G,是连通且无,奇度顶点.,无向图,G,含有欧拉通路、但没有欧拉回路当且仅当,G,是连,通且有2个奇度顶点,其余顶点均为偶度数.这2个奇,度顶点是每条欧拉通路端点.,推论,无向图,G,是欧拉图当且仅当,G,是连通且无奇度顶点,9/19,9,实例,无欧拉通路,欧拉图,欧拉图,有欧拉通路,非欧拉图,有欧拉通路,非欧拉图,无欧拉通路,10/19,10,欧拉图判别定理(续),定理6.9,有向图,D,有欧拉回路当且仅当,D,是连通且全部,顶点入度等于出度.,有向图,D,有欧拉通路、但没有欧拉回路当且仅当,D,是连通,且有一个顶点入度比出度大1、一个顶点入度比出,度小1,其余顶点入度等于出度.,推论,有向图,D,是欧拉图当且仅当,D,是连通且全部顶点,入度等于出度.,11/19,11,实例,欧拉图,无欧拉通路,无欧拉通路,有欧拉通路,无欧拉回路,无欧拉通路,有欧拉通路,无欧拉回路,12/19,12,周游世界问题(,W.Hamilton,1859,年),13/19,13,哈密顿回路与哈密顿通路,哈密顿通路,:经过图中全部顶点一次且仅一次通路.,哈密顿回路,:经过图中全部顶点一次且仅一次回路.,哈密顿图,:含有哈密顿回路图.,说明：,哈密顿通路是初级通路,哈密顿回路是初级回路,有哈密顿通路不一定有哈密顿回路,环与平行边不影响图哈密顿性,14/19,14,哈密顿图必要条件,定理6.10,若无向图,G,=,是哈密顿图,则对于,V,任意,非空真子集,V,1,都有,p,(,G,V,1,),|,V,1,|.,证 设,C,为,G,中一条哈密顿回路,有,p,(,C,V,1,),|,V,1,|.,又因为,C,G,故,p,(,G,V,1,),p,(,C,V,1,),|,V,1,|.,比如,当,r,s,时,K,r,s,不是哈密顿图,推论,有割点图不是哈密顿图,15/19,15,实例,例2,证实下述各图不是哈密顿图:,(,a),(,b),(,c),(,c),中存在哈密顿通路,16/19,16,实例,例3,证实右图不是哈密顿图,证 假设存在一条哈密顿回路,a,f,g,是2度顶点,边(,a,c,),(,f,c,),和,(,g,c,),必在这条哈密顿回路上,从而点,c,出现3次,矛盾.,a,b,c,d,e,f,g,另外,该图满足定理6.10条件,这表明此条件是必要、,而不充分.,又,该图有哈密顿通路.,17/19,17,存在哈密顿回路(通路)充分条件,定理6.11,设,G,是,n,(,n,3),阶无向简单图,若任意两个不相邻,顶点度数之和大于等于,n,1,则,G,中存在哈密顿通路;,若任意两个不相邻顶点度数之和大于等于,n,则,G,中,存在哈密顿回路,即,G,为哈密顿图.,推论,设,G,是,n,(,n,3),阶无向简单图,若,(,G,),n,/2,则,G,是哈密,顿图,当,n,3,时,K,n,是哈密顿图;当,r,=,s,2,时,K,r,s,是哈密顿图.,定理6,12,设,D,是,n,(,n,2,),阶有向图,若略去全部边方向后,所得无向图中含子图,K,n,则,D,中有哈密顿通路.,18/19,18,应用,例4,有7个人,A,会讲英语,B,会讲英语和汉语,C,会讲英语、,意大利语和俄语,D,会讲日语和汉语,E,会讲德语和意大利,语,F,会讲法语、日语和俄语,G,会讲法语和德语.问能否将,他们沿圆桌安排就坐成一圈,使得每个人都能与两旁人,交谈?,解,作无向图,每人是一个顶点,2人之间有边,他们有共同语言.,A,B,C,D,E,F,G,ACEGFDBA,是一条哈密顿回路,按此次序就坐即可.,19/19,19,