《离散数学--6.4几种特殊的图》由会员分享，可在线阅读，更多相关《离散数学--6.4几种特殊的图（19页珍藏版）》请在金锄头文库上搜索。
1、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,二部图的判别定理,
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中任意两点不相邻.,4,实例,非二部图,非二部图,5,实例,例1 某中学有3个课外活动小
3、组:数学组, 计算机组和生物 组. 有赵,钱,孙,李,周5名学生, 问分别在下述3种情况下, 能 否选出3人各任一个组的组长? (1) 赵, 钱为数学组成员, 赵,孙,李为计算机组成员, 孙,李, 周为生物组成员. (2) 赵为数学组成员, 钱,孙,李为计算机组成员, 钱,孙,李,周 为生物组成员. (3) 赵为数学组和计算机组成员, 钱,孙,李,周为生物组成员.,6,实例(续),解,(1),(2)有多种方案, (3) 不可能,7,欧拉图,哥尼斯堡七桥,8,欧拉图,欧拉通路:经过所有边且每条边恰好经过一次的通路 欧拉回路:经过所有边且每条边恰好经过一次的回路 欧拉图:有欧拉回路的图说明： 上述
4、定义对无向图和有向图都适用 规定平凡图为欧拉图 欧拉通路是简单通路, 欧拉回路是简单回路 环不影响图的欧拉性,9,欧拉图判别定理,定理6.8 无向图G具有欧拉回路当且仅当G是连通的且无 奇度顶点. 无向图G具有欧拉通路、但没有欧拉回路当且仅当G是连 通的且有2个奇度顶点, 其余顶点均为偶度数的. 这2个奇 度顶点是每条欧拉通路的端点.推论 无向图G是欧拉图当且仅当G是连通的且无奇度顶点,10,实例,无欧拉通路,欧拉图,欧拉图,有欧拉通路 非欧拉图,有欧拉通路 非欧拉图,无欧拉通路,11,欧拉图判别定理(续),定理6.9 有向图D有欧拉回路当且仅当D是连通的且所有 顶点的入度等于出度. 有向图D
5、有欧拉通路、但没有欧拉回路当且仅当D是连通 的且有一个顶点的入度比出度大1、一个顶点的入度比出 度小1, 其余的顶点的入度等于出度.推论 有向图D是欧拉图当且仅当D是连通的且所有顶点的 入度等于出度.,12,实例,欧拉图,无欧拉通路,无欧拉通路,有欧拉通路 无欧拉回路,无欧拉通路,有欧拉通路 无欧拉回路,13,周游世界问题(W.Hamilton, 1859年),14,哈密顿回路与哈密顿通路,哈密顿通路: 经过图中所有顶点一次且仅一次的通路. 哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图.说明： 哈密顿通路是初级通路 哈密顿回路是初级回路 有哈密顿通路不一定
6、有哈密顿回路 环与平行边不影响图的哈密顿性,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)必在这条哈密
7、顿回路上, 从而点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是一条哈密顿回路, 按此顺序就坐即可.,
