《二部图欧拉图哈密尔顿图平面图教学课件.ppt》由会员分享，可在线阅读，更多相关《二部图欧拉图哈密尔顿图平面图教学课件.ppt（20页珍藏版）》请在三一文库上搜索。
1、 8.1 二部图 8.2 欧拉图 8.3 哈密尔顿图 8.4 平面图 第八章 一些特殊的图 1 若能将无向图G=的顶点集V划分 成两个子集V1和V2(V1V2=),使得G中任 何一条边的两个端点一个属于V1,另一个属 于V2,则称G为二部图(也称为偶图).V1,V2称 为互补顶点子集,此时可将G记成G=,若V1 =n, V2=m,则记完全二部图 G为Kn,m. 二部图 定义 在下图中,(1)所示为K2,3,(2)所示 为K3,3. K3,3是重要的完全二部图,它与 K5一起在平面图中起着重要作用. 判断二部图的定理 一个无向图G=是二部图当 且仅当G中无奇数长度的回路. 图8.2 12 3 4
2、5 6 62 4 153 图8.2所示3个图中,均无奇数长度的 回路,所以,它们都是二部图. 其中图(2)所示为K2,3,图(3)所示为 K3,3,它们分别与图8.1中(1),(2)所示 的图同构. 设G=为无向图,E*E,若E*中任意 两条边均不相邻,则称E*为G中的匹配(或边独 立集). 若在E*中再加入任何1条边就都不是匹配 了,则称E*为极大匹配. 边数最多的极大匹配称为最大匹配,最大 匹配中的元素(边)的个数称为G的匹配数,记为 1(G),简记为1. 匹 配 今后常用M表示匹配.设 M为G中一个匹配.vV(G),若 存在M中的边与v关联,则称v为 M饱和点,否则称v为M非饱和 点,若
3、G中每个顶点都是M饱和 点,则称M为G中完美匹配. 在图 (1)中，e1,e1,e7,e5,e4,e6 等都是图中的匹配.其中e5,e1,e7,e4,e6 是极大匹配,e1,e7,e2,e6是最大匹配,匹 配数1=2. 图中不存在完美匹配. 在图(2)中,e2,e5,e3,e6,e1,e7,e4都 是极大匹配,其中e1,e7,e4是最大匹配, 同时也是完美匹配,匹配数为3. 完备匹配 u设G=为一个二部 图,M为G中一个最大匹配,若M =minV1,V2,则称M 为G中的一 个完备匹配. u此时若V1 V2,则称M为V1 到V2的一个完备匹配.如果V1= V2,这时M为G中的完美匹配. 图8.
4、4 存在完备匹配吗?存在完美匹配吗?. Hall定理 设二部图G=,V1V2,G 中存在从V1到V2的完备匹配当且仅当V1 中任意k个顶点(k=1,2, V1)至少邻接 V2中的k个顶点. 设二部图G=,如果 u (1)V1中每个顶点至少关联t(t0) 条边; u (2)V2中每个顶点至多关联t条边, 则G中存在V1到V2的完备匹配. lHall定理中的条件称为“相异性条件”, 定理8.3中的条件称为“t条件”,满足t条件的 二部图,一定满足相异性条件. l事实上,由条件(1)可知,V1中k个顶点至 少关联kt条边.由条件(2)可知,这kt条边至少 关联V2中的k个顶点,于是若G满足t条件,则
5、 G一定满足相异性条件,但反之不真. 例8.1 某中学有3个课外小组:物理组 、化学组、生物组.今有张、王、李、赵 、陈5名同学.若已知: l (1)张、王为物理组成员,张、李、 赵为化学组成员,李、赵、陈为生物组成 员; l (2)张为物理组成员,王、李、赵为 化学组成员,王、李、赵、陈为生物组成 员; l (3)张为物理组和化学组成员,王、 李、赵、陈为生物组成员. 问在以上3种情况下能否各选出3名 不兼职的组长？ 解: 设v1,v2,v3,v4,v5分别表示张、王、 李、赵、陈.u1,u2,u3分别表示物理组、化 学组、生物组.在3种情况下作二部图分别 记为G1,G2,G3,如图8.5所示. 图8.5 G1满足t=2的t条件,所以,存在从 V1=u1,u2,u3到V2=v1,v2,v3,v4,v5的完 备匹配,图中粗边所示的匹配就是其中 的一个,即选张为物理组组长、李为化 学组组长、赵为生物组组长. G2不满足t条件,但满足相异性 条件,因而也存在完备匹配,图中粗 边所示匹配就是其中的一个完备匹 配. G3不满足t条件,也不满足相异 性条件,因而不存在完备匹配,故选 不出3名不兼职的组长来.