离散数学-6.4几种特殊的图

《离散数学-6.4几种特殊的图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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和V2为互补顶点子集.又若G是简单图,且V1中每个顶点均与V2中每个顶点都相邻,则称G为完全二部图,记为Kr,s,其中r=

2、V1

3、,s=

4、V2

5、.K23K332二部图的判别定理定理6

6、.7无向图G=是二部图当且仅当G中无奇长度的回路证必要性.设G=是二部图,每条边只能从V1到V2,或从V2到V1,故任何回路必为偶长度.充分性.不妨设G至少有一条边且连通.取任一顶点u,令V1={v

7、vVd(v,u)为偶数},V2={v

8、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个

9、课外活动小组:数学组,计算机组和生物组.有赵,钱,孙,李,周5名学生,问分别在下述3种情况下,能否选出3人各任一个组的组长?(1)赵,钱为数学组成员,赵,孙,李为计算机组成员,孙,李,周为生物组成员.(2)赵为数学组成员,钱,孙,李为计算机组成员,钱,孙,李,周为生物组成员.(3)赵为数学组和计算机组成员,钱,孙,李,周为生物组成员.5实例(续)解(1),(2)有多种方案,(3)不可能(1)数计生赵钱孙李周(2)数计生赵钱孙李周(3)数计生赵钱孙李周6欧拉图哥尼斯堡七桥7欧拉图欧拉通路:经过所有边且每条边恰好经过一次的通路欧拉回路:经过所有边且每条边恰好经过一

10、次的回路欧拉图:有欧拉回路的图说明：上述定义对无向图和有向图都适用规定平凡图为欧拉图欧拉通路是简单通路,欧拉回路是简单回路环不影响图的欧拉性8欧拉图判别定理定理6.8无向图G具有欧拉回路当且仅当G是连通的且无奇度顶点.无向图G具有欧拉通路、但没有欧拉回路当且仅当G是连通的且有2个奇度顶点,其余顶点均为偶度数的.这2个奇度顶点是每条欧拉通路的端点.推论无向图G是欧拉图当且仅当G是连通的且无奇度顶点9实例无欧拉通路欧拉图欧拉图有欧拉通路非欧拉图有欧拉通路非欧拉图无欧拉通路10欧拉图判别定理(续)定理6.9有向图D有欧拉回路当且仅当D是连通的且所有顶点的入度等于出度

11、.有向图D有欧拉通路、但没有欧拉回路当且仅当D是连通的且有一个顶点的入度比出度大1、一个顶点的入度比出度小1,其余的顶点的入度等于出度.推论有向图D是欧拉图当且仅当D是连通的且所有顶点的入度等于出度.11实例欧拉图无欧拉通路无欧拉通路有欧拉通路无欧拉回路无欧拉通路有欧拉通路无欧拉回路12周游世界问题(W.Hamilton,1859年)13哈密顿回路与哈密顿通路哈密顿通路:经过图中所有顶点一次且仅一次的通路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.说明：哈密顿通路是初级通路哈密顿回路是初级回路有哈密顿通路不一定有哈密顿回路环

12、与平行边不影响图的哈密顿性14哈密顿图的必要条件定理6.10若无向图G=是哈密顿图,则对于V的任意非空真子集V1均有p(GV1)

13、V1

14、.证设C为G中一条哈密顿回路,有p(CV1)

15、V1

16、.又因为CG,故p(GV1)p(CV1)

17、V1

18、.例如当r≠s时,Kr,s不是哈密顿图推论有割点的图不是哈密顿图15实例例2证明下述各图不是哈密顿图:(a)(b)(c)(c)中存在哈密顿通路16实例例3证明右图不是哈密顿图证假设存在一条哈密顿回路,a,f,g是2度顶点,边(a,c),(f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次,矛盾

19、.abcdefg此外,该图满足定理6.10的条件,这表明此条件是必要、而不充分的.又,该图有哈密顿通路.17存在哈密顿回路(通路)的充分条件定理6.11设G是n(n3)阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于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)阶有向图,若略去所有边的方向后所得无向图中含子图Kn,则D中有哈密

20、顿通路.18应用例4有7个人,A会讲英