离散数学-6.4几种特殊的图.ppt
1,6.4 几种特殊的图,6.4.1 二部图二部图的充要条件6.4.2 欧拉图欧拉回路(通路)及其存在的充要条件6.4.3 哈密顿图哈密顿回路(通路)及其存在的必要条件和充分条件6.4.4 平面图,2,二部图,定义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|.,3,二部图的判别定理,定理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中任意两点不相邻.,4,实例,非二部图,非二部图,5,实例,例1 某中学有3个课外活动小组:数学组,计算机组和生物组.有赵,钱,孙,李,周5名学生,问分别在下述3种情况下,能否选出3人各任一个组的组长?(1)赵,钱为数学组成员,赵,孙,李为计算机组成员,孙,李,周为生物组成员.(2)赵为数学组成员,钱,孙,李为计算机组成员,钱,孙,李,周为生物组成员.(3)赵为数学组和计算机组成员,钱,孙,李,周为生物组成员.,6,实例(续),解,(1),(2)有多种方案,(3)不可能,7,欧拉图,哥尼斯堡七桥,8,欧拉图,欧拉通路:经过所有边且每条边恰好经过一次的通路 欧拉回路:经过所有边且每条边恰好经过一次的回路欧拉图:有欧拉回路的图说明：上述定义对无向图和有向图都适用规定平凡图为欧拉图欧拉通路是简单通路,欧拉回路是简单回路环不影响图的欧拉性,9,欧拉图判别定理,定理6.8 无向图G具有欧拉回路当且仅当G是连通的且无奇度顶点.无向图G具有欧拉通路、但没有欧拉回路当且仅当G是连通的且有2个奇度顶点,其余顶点均为偶度数的.这2个奇度顶点是每条欧拉通路的端点.推论 无向图G是欧拉图当且仅当G是连通的且无奇度顶点,10,实例,无欧拉通路,欧拉图,欧拉图,有欧拉通路非欧拉图,有欧拉通路非欧拉图,无欧拉通路,11,欧拉图判别定理(续),定理6.9 有向图D有欧拉回路当且仅当D是连通的且所有顶点的入度等于出度.有向图D有欧拉通路、但没有欧拉回路当且仅当D是连通的且有一个顶点的入度比出度大1、一个顶点的入度比出度小1,其余的顶点的入度等于出度.推论 有向图D是欧拉图当且仅当D是连通的且所有顶点的入度等于出度.,12,实例,欧拉图,无欧拉通路,无欧拉通路,有欧拉通路无欧拉回路,无欧拉通路,有欧拉通路无欧拉回路,13,周游世界问题(W.Hamilton,1859年),14,哈密顿回路与哈密顿通路,哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.说明：哈密顿通路是初级通路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路环与平行边不影响图的哈密顿性,15,哈密顿图的必要条件,定理6.10 若无向图G=是哈密顿图,则对于V的任意非空真子集V1均有 p(GV1)|V1|.证 设C为G中一条哈密顿回路,有p(CV1)|V1|.又因为CG,故 p(GV1)p(CV1)|V1|.例如 当rs时,Kr,s不是哈密顿图推论 有割点的图不是哈密顿图,16,实例,例2 证明下述各图不是哈密顿图:,(a),(b),(c),(c)中存在哈密顿通路,17,实例,例3 证明右图不是哈密顿图,证 假设存在一条哈密顿回路,a,f,g是2度顶点,边(a,c),(f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次,矛盾.,此外,该图满足定理6.10的条件,这表明此条件是必要、而不充分的.又,该图有哈密顿通路.,18,存在哈密顿回路(通路)的充分条件,定理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中有哈密顿通路.,19,应用,例4 有7个人,A会讲英语,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?解,作无向图,每人是一个顶点,2人之间有边他们有共同的语言.,ACEGFDBA是一条哈密顿回路,按此顺序就坐即可.,
