二部图欧拉图哈密尔顿图平面

《二部图欧拉图哈密尔顿图平面》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.1二部图8.2欧拉图8.3哈密尔顿图8.4平面图第八章一些特殊的图1若能将无向图G=的顶点集V划分成两个子集V1和V2(V1∩V2=),使得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=是二部图当

2、且仅当G中无奇数长度的回路.图8.2123456624153图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中一个匹配.v∈V(

3、G),若存在M中的边与v关联,则称v为M饱和点,否则称v为M非饱和点,若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.完备匹配设G=为一个二部图,M为G中一个最

4、大匹配,若M=min{V1,V2},则称M为G中的一个完备匹配.此时若V1≤V2,则称M为V1到V2的一个完备匹配.如果V1=V2,这时M为G中的完美匹配.图8.4存在完备匹配吗?存在完美匹配吗?.Hall定理设二部图G=,V1≤V2,G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点(k=1,2,…V1)至少邻接V2中的k个顶点.设二部图G=,如果(1)V1中每个顶点至少关联t(t＞0)条边;(2)V2中每个顶点至多关联t条边,则G中存在V1到V2的完备

5、匹配.Hall定理中的条件称为“相异性条件”,定理8.3中的条件称为“t条件”,满足t条件的二部图,一定满足相异性条件.事实上,由条件(1)可知,V1中k个顶点至少关联kt条边.由条件(2)可知,这kt条边至少关联V2中的k个顶点,于是若G满足t条件,则G一定满足相异性条件,但反之不真.例8.1某中学有3个课外小组:物理组、化学组、生物组.今有张、王、李、赵、陈5名同学.若已知:(1)张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员;(2)张为物理组成员,王、李、赵为化学组成员,王、李、赵、陈为生物组成员;(3)张为物

6、理组和化学组成员,王、李、赵、陈为生物组成员.问在以上3种情况下能否各选出3名不兼职的组长？解:设v1,v2,v3,v4,v5分别表示张、王、李、赵、陈.u1,u2,u3分别表示物理组、化学组、生物组.在3种情况下作二部图分别记为G1,G2,G3,如图8.5所示.图8.5G1满足t=2的t条件,所以,存在从V1={u1,u2,u3}到V2={v1,v2,v3,v4,v5}的完备匹配,图中粗边所示的匹配就是其中的一个,即选张为物理组组长、李为化学组组长、赵为生物组组长.G2不满足t条件,但满足相异性条件,因而也存在完备匹配,图中粗边所示匹

7、配就是其中的一个完备匹配.G3不满足t条件,也不满足相异性条件,因而不存在完备匹配,故选不出3名不兼职的组长来.