清华离散数学(第2版)64

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