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