离散数学 课件6.1 二部图

6.1二部图定义设无向图G=<V,E>,若能将V划分成V1和V2

，(V1

V2=V,V1

V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,称V1和V2为互补顶点子集.若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.

注意:n阶零图为二部图.不是定理无向图G=<V,E>是二部图当且仅当G中无奇圈

应用举例：已知：a，b，c，d，e，f，g的下述事实：(a)说汉语、日语；(b)说日语、法语；(c)说德语、法语、西班牙语；(d)说汉语、德语、俄语、葡萄牙语；(e)说俄语、朝语；(f)说朝语、西班牙语；(g)说葡萄牙语。试问：能否将七个人分成两组，使同一组中没有两个人能互相交谈？并用图论方法，说明你的结论。abcdefg定义

设G=(V,E)为无向图,M⊆E（1）若M中任意两条边均不相邻，则称M为G中的匹配。即边

独立集。（2）若在M中再加入任何一条边就都不是匹配了,则称M为极大匹配。（3）边数最多的匹配称为最大匹配,最大匹配中边的条数称为G的匹配数。（4）设M为G中一个匹配,v∈V,若存在M中的边与v关联,则称v为M饱和点,否则称v为M非饱和点。若G中每个结点都是M饱和点,则称M为完美匹配。注

最大匹配是极大匹配,但反之不真。极大匹配最大匹配

1=3M1M2

关于M1,a,b,e,d是饱和点

f,c是非饱和点

M1不是完美匹配

M2是完美匹配

在左图中,{e1}、{e1,e10}、{e5,e8}、{e7}、{e1,e4,e8}等都是图中的匹配,其中{e5,e8}、{e1,e4,

e8}是极大匹配,{e1,e4，e8}是最大匹配，匹配数为3，{e1,e4，e8}是完美匹配。

在右图中,{e1,e4}、{e3,e5}、{e2,e6}、{e1,e6}等都是极大匹配,同时也是最大匹配,匹配数为2，图中有奇数个顶点，不存在完美匹配。

定义

设G=(V1,E,V2)为一个偶图,|V1|≤|V2|,M为G中一个最大匹配,若|M|=|V1|,则称M为G中V1到V2的完备匹配。

当|V1|=|V2|时,完备匹配是完美匹配。完备,不完美不完备完美

例

班上四名同学竞选干部:班长、团支书、副班长、学习委员。竞聘的四位候选者分别是小王、小赵、小钱、小孙。小赵竞聘班长和团支书，小钱竟聘班长和副班长，小孙竞聘学习委员，副班长，小王竟聘学习委员和团支书。如果四位同学都竞聘成功，能否使得每位同学担任自己竞聘的职务?

解

设A、B、C、D分别表示小王、小赵、小钱、小孙，v1、v2、v3、v4分别表示班长、团支书、副班长、学习委员，根据题意可得图如下此图存在一个完备匹配(A,v2),(B,v1),(C,v3),(D,v4)，表示小王担任团支书，小赵担任班长，小钱担任副班长，小孙担任学习委员。定理设二部图G=(V1,E,V2)，|V1|≤|V2|,G中存在从V1到V2的完备匹配当且仅当V1中任意k个结点至少邻接V2中的k个结点,k=1,2,⋯,V1。此定理称为Hall定理。定理

设二部图G=(V1,E,V2),如果存在t>0使得:(1)V1中每个结点至少关联t条边;(2)V2中每个结点至多关联t条边，则G中存在V1到V2的完备匹配。Hall定理中的条件称为相异性条件,另一定理称为t条件。相异性条件是二部图存在完备匹配的充分必要条件，而t条件只是二部图存在完备匹配的充分条件,不是必要条件。

例

某课题组要从小王、小赵、小钱、小孙、小张5人中选派3人到上海、广州、香港去开会，若已知(1)小王、小钱想去上海，小王、小赵、小孙想去广州,小钱、小张想去香港;(2)小王想去上海,小钱、小赵、小孙、小张想去广州,小赵、小钱、小张想去香港;(3)小王想去上海和广州，

小赵、小钱、小孙、小张想去香港。在以上3种情况下能否在满足个人要求的条件下选出派遣方案?

解

设v1、v2、v3、v4、v5分别表示小王、小赵、小钱、小孙、小张。A、B、C分别表示上海、广州、香港。在3种情况下作二部图分别记为G1、G₂、G₃G1满足t=2的t条件,也满足相异性条件，所以存在从V1={A、B、C}到V₂={v1、v2、v3、v4、v5}的完备匹配,(A,v3),(B,v1),(C,v5)就是其中的一个,即派小钱到上海，小王到广州，小张到香港。G2满足相异性条件,也存在完备匹配