chapter13支配集、覆盖集、独立集与匹配2014.5.25

1、第十三章第十三章 支配集、覆盖集、独支配集、覆盖集、独立集与匹配立集与匹配中国海洋大学中国海洋大学计算机系计算机系主要内容主要内容n支配集支配集,独立集独立集,点覆盖点覆盖,团团n边覆盖边覆盖, 边独立集边独立集(匹配匹配)n最大匹配最大匹配, Berge定理定理n完备匹配完备匹配, Hall条件条件, t条件条件n完美匹配完美匹配, Tutte定理定理支配集(dominating set)n无向图无向图G=, V*Vn支配集支配集: u(uV-V*v(vV*(u,v)E) 或或 uV-V*, vV*, uEvn极小支配集极小支配集: V*是支配集是支配集, 其真子集都不是其真子集都不是n最小

2、支配集最小支配集: |V*|最小的支配集最小的支配集n支配数支配数: 0(G)=|V*|, V*是最小支配集是最小支配集支配集(例)n星形图星形图Sn: v0,v1, v2, vn-1, 0(Sn)=1n轮图轮图Wn: v0,v1, v3, v5 ,vn-2, 0(Wn)=1v1v2v3v4v5v0v1v2v3v4v5v0v1v2v3v4v5v0定理13.1n定理定理13.1: 无向图无向图G无孤立点无孤立点,V1*是极小支配集是极小支配集,则存则存在在V2*也是极小支配集也是极小支配集,且且V1*V2*= .证明证明: V1*是极小支配集是极小支配集,则则V-V1*也是支配集也是支配集.(反

3、证反证: 否否则则, uV1*, vV-V1*,(u,v) E, V1*-u还是支配集还是支配集,矛盾矛盾.) V-V1*是支配集是支配集,则则V-V1*中有子集是极小支配集中有子集是极小支配集,设设为为V2*. 则则V1*V2*= . #V1*V-V1*uV1*-uV-V1*u独立集(independent set)n无向图无向图G=, V*Vn独立集独立集: u,vV*, (u,v) En极大独立集极大独立集: V*是独立集是独立集, 其真母集都不是其真母集都不是n最大独立集最大独立集: |V*|最大的独立集最大的独立集n独立数独立数: 0(G)=|V*|, V*是最大独立集是最大独立集独

4、立集(例)nv0, v1,v4, v2,v4,v6, 0=3v1v0v2v1v0v2v4v1v0v2v4v6定理13.2n定理定理13.2: 无向图无向图G无孤立点无孤立点,V*是是极大独立集极大独立集,则则V*也是也是极小支配集极小支配集.【思路思路】先证先证V*是支配集；再证是支配集；再证V*是极小支配集是极小支配集.证明证明: 证证V*是支配集是支配集. (反证反证) 设设V*不是支配集不是支配集, 则则uV-V*, vV*,(u,v) E, V*u还是独立集还是独立集,矛盾矛盾.再证再证V*是极小支配集是极小支配集.(反证反证) 否则否则, uV*, V*-u是支配集是支配集, 则则v

5、V*, (u,v)E, 与与V*是独立集相矛盾是独立集相矛盾. #定理定理13.2(讨论讨论)n定理定理13.2: (无孤立点图无孤立点图)极大独立集是极小支配集极大独立集是极小支配集 但逆命题不成立但逆命题不成立n反例反例: v2,v3是极小支配集是极小支配集,但不是独立集但不是独立集, 更不是极大独立集更不是极大独立集v1v2v3v4点覆盖(vertex cover)n无向图无向图G=, V*Vn点覆盖点覆盖: e(eEv(vV*v关联关联e) 或或 eE, vV*, v关联关联en极小点覆盖极小点覆盖: V*是点覆盖是点覆盖, 其真子集都不是其真子集都不是n最小点覆盖最小点覆盖: |V*

6、|最小的点覆盖最小的点覆盖n点覆盖数点覆盖数: 0(G)=|V*|, V*是最小点覆盖是最小点覆盖点覆盖(例)n v0,v1,v3,v5, v1, v2, v3, v4, v5, v6, 0=4v1v0v2v3v5v1v0v2讨论(点覆盖与支配集)n (连通图连通图)点覆盖是支配集点覆盖是支配集n极小点覆盖不一定是极小支配集极小点覆盖不一定是极小支配集. 反例反例:v0, v1, v3, v5是极小点覆盖是极小点覆盖, v1, v3, v5是极小支配集是极小支配集n支配集不一定是点覆盖支配集不一定是点覆盖. 反例反例: v1,v4是支配集是支配集,不是不是点覆盖点覆盖v1v0v2v3v5v1v

7、0v2v3v5定理13.3（点覆盖与独立集）n定理定理13.3: 无向图无向图G无孤立点无孤立点, V*V, V*是点覆盖是点覆盖 V-V*是独立集是独立集.n证明证明: () (反证反证) 否则否则, u,vV-V*, (u,v)E, 显然显然V*不是点覆盖不是点覆盖,矛盾矛盾. ( ) V-V*是独立集是独立集, (u,v)E, u V-V* v V-V*, uV* vV*, V*是点覆盖是点覆盖. #定理13.3的推论n推论推论: 无向图无向图G无孤立点无孤立点, V*是极是极(最最)小点小点 覆盖覆盖V-V*是极是极(最最)大独立集大独立集. 0+ 0=n.#n例例 最大独立集有最大独

8、立集有v1, v3, v5和和v2, v4, v6, 0=3 从而最小点覆盖集有从而最小点覆盖集有v0, v2, v4, v6和和v0, v1, v3, v5, 0=4.v1v0v2v3v5团(clique)n无向图无向图G=, V*Vn团团: GV*是完全子图是完全子图n极大团极大团: V*是团是团, 其真母集都不是其真母集都不是n最大团最大团: |V*|最大的团最大的团n团数团数: 0(G)=|V*|, V*是最大团是最大团团(例)n v0, v1, v2, v1, v2, v1, 0=3v1v0v2v3v5v1v0v2v3v5v1v0v2v3v5定理13.4n定理定理13.4: 无向图无

9、向图G, V*是是G的团的团 V*是是G的独立集的独立集. #n推论推论: 无向图无向图G, V*是是G的极的极(最最)大团大团V*是是G的极的极(最最)大独立集大独立集. 0(G)= 0 (G). #n总结总结: 0+ 0=n(无孤立点无孤立点). 0(G)= 0(G). 所以所以 0, 0, 0三者互相确定三者互相确定, 但都是难解的但都是难解的(目前都没目前都没有多项式时间算法有多项式时间算法)n研究图研究图G的的团团可转化为研究可转化为研究G的的独立集独立集，反之依然，反之依然.例13.1n例例13.1: 求全体极小支配集求全体极小支配集,极小点覆盖极小点覆盖,极大独立集极大独立集解解

10、: (1)极小支配集极小支配集.vV(v+u(v)u)=(a+b)(b+a+c+d)(c+b+d)(d+c+b)=(a+b)(b+c+d)=b+(a(c+d)=ac+ad+b. (幂等幂等: a+a=a,aa=a, 逻辑加乘逻辑加乘(即即“ ”,“ ”)a,c, a,d, b是全体极小支配集是全体极小支配集. 0=1abcd例13.1(续)n例例13.1: 求全体极小支配集求全体极小支配集,极小点覆盖极小点覆盖,极大独立集极大独立集解解: (2)极小点覆盖极小点覆盖.(u,v)E(u+v)=(a+b)(b+c)(b+d)(c+d)=bc+bd+acd. (幂等幂等: a+a=a,aa=a, 逻

11、辑加乘逻辑加乘(即即“ ”,“ ”)b,c, b,d, a,c,d是全体极小点覆盖是全体极小点覆盖. 0=2.abcd例13.1(续)n例例13.1: 求全体极小支配集求全体极小支配集,极小点覆盖极小点覆盖,极大独立集极大独立集解解:(3)极大独立集极大独立集. G无孤立点无孤立点, V*是极小点覆盖是极小点覆盖 V-V*是极大独立集是极大独立集. b,c,b,d,a,c,d是全体极小点覆盖是全体极小点覆盖, a,d,a,c,b是全体极大独立集是全体极大独立集. 0=2. #abcd边覆盖(edge cover)n无向图无向图G=, E*En边覆盖边覆盖: vV, eE*, e关联关联vn极小

12、边覆盖极小边覆盖: E*是边覆盖是边覆盖, 其真子集都不是其真子集都不是n最小边覆盖最小边覆盖: |E*|最小的边覆盖最小的边覆盖n边覆盖数边覆盖数: 1(G)=|E*|, E*是最小边覆盖是最小边覆盖边覆盖(例)ne2,e3,e6, e2,e3,e7, 1=3e1e2e3e4e5e6e7e1e2e3e4e5e6e7e1e2e3e4e5e6e7匹配(matching)n无向图无向图G=, E*En匹配匹配(边独立集边独立集): e,fE*, e,f不相邻不相邻n极大匹配极大匹配: E*是匹配是匹配, 其真母集都不是其真母集都不是n最大匹配最大匹配: |E*|最大的匹配最大的匹配n匹配数匹配数:

13、 1(G)=|E*|, E*是最大匹配是最大匹配匹配(例)ne1, e7, e1, e4, e5,1=2e1e2e3e4e5e6e7e1e2e3e4e5e6e7e1e2e3e4e5e6e7e1e2e3e4e5e6e7定理13.5n定理定理13.5: 无向图无向图G无孤立点无孤立点, (1) 设设M是最大匹配是最大匹配, 非饱和点非饱和点v, 取取v关联的一边关联的一边, 组成边集组成边集N, 则则W=MN是最小边覆盖是最小边覆盖. (2) 设设W1是最小边覆盖是最小边覆盖, 若若W1中有相邻边中有相邻边,就删除其就删除其中一边中一边, 直到无相邻边为止直到无相邻边为止,设删除的边组成边集设删除

14、的边组成边集N1, 则则M1=W1-N1是最大匹配是最大匹配 (3) 1+ 1=n定理13.5(证明)n证明证明: M是最大匹配是最大匹配, |M|= 1, |N|=n-2 1, 1|W|=|M|+|N|=n- 1.(*) 令令W1是最小边覆盖是最小边覆盖, |W1|= 1, 在在W1中每删除中每删除1边恰产边恰产生生1个非饱和点个非饱和点,因此由因此由W1构造构造M1时有时有, |N1|=|W1|-|M1|=“删除边数删除边数”=“M1的非饱和点数的非饱和点数” =n-2|M1|, 1=|W1|=n-|M1|n- 1.(*)由由(*)(*), n 1+ 1n, 所以所以 1+ 1 =n.由由

15、(*), |W|= 1, W是最小边覆盖是最小边覆盖.由由(*), |M1|= 1, M1是最大匹配是最大匹配. #定理13.6n定理定理13.6: 无向图无向图G无孤立点无孤立点, M是匹配是匹配,N是点覆盖是点覆盖, Y是独立集是独立集, W是边覆盖是边覆盖, 则则 (1) |M|N|, (2) |Y|W|, (3) 等号成立时等号成立时, M是最大匹是最大匹配配, N是最小点覆盖是最小点覆盖, Y是最大独立集是最大独立集, W是最小边覆是最小边覆盖盖.n证明证明: (1) M中边不相邻中边不相邻, 至少需要至少需要|M|个点才能覆盖个点才能覆盖M. (2) Y中顶点不相邻中顶点不相邻,

16、至少需要至少需要|Y|条边才能覆盖条边才能覆盖Y. (3) |M|=|N|说明说明|M|达到最大值达到最大值, |N|达到最小值达到最小值. |Y|=|W|类似类似. #推论n推论推论: 无向图无向图G无孤立点无孤立点, 则则 1 0, 0 1. #nKr,s: 1= 0=minr,s, 0 = 1=maxr,s,n总结总结: 无向图无向图G无孤立点无孤立点, 则则 1 0( 0,?) 0= 0 1. 0+ 0 =n, 1+ 1 =n,完美匹配, 完备匹配n完美匹配完美匹配(perfect matching): 没有非饱和点的匹配没有非饱和点的匹配n完备匹配完备匹配(complete matc

17、hing) : G=是二部图是二部图, |V1|V2|,|M|=|V1|n求最小边覆盖求最小边覆盖, 最大匹配最大匹配, 完美匹配完美匹配, 都是都是易解的易解的(有有多项式时间算法多项式时间算法) 课后作业：查找以上三个问题的算法，用形式化语课后作业：查找以上三个问题的算法，用形式化语言描写出来。言描写出来。完美匹配(例)e1e2e3e4e5e6e7e8e1e2e3e4e5e6e7e8e1e2e3e4e5e6e7e8e1e2e3e4e5e6e7e8饱和点,交错路径,增广路径n设设M是是G中匹配中匹配n饱和点饱和点: v与与M中边关联中边关联n非饱和点非饱和点: v不与不与M中边关联中边关联n

18、交错路径交错路径: 在在M和和E-M中交替取边的路径中交替取边的路径n可增广交错路径可增广交错路径: 两端都是非饱和点的交错路径两端都是非饱和点的交错路径举例举例-交错路径交错路径e1e2e3e4e5e6e7e8e1e2e3e4e5e6e7e8饱和点与非饱和点饱和点与非饱和点交错路径交错路径e1e2e3e4e5e6e7e8交错圈交错圈举例举例-可增广交错路径可增广交错路径e1e2e3e4e5e6e7e8可增广交错路径可增广交错路径e1e2e3e4e5e6e7e8更长的匹配更长的匹配最大匹配n定理定理13.7: 设设M1,M2是是G中中2个不同匹配个不同匹配,则则GM1 M2的每个连通分支是的每

19、个连通分支是M1,M2中的边组成的中的边组成的交错圈交错圈或或交交错路径错路径n证明证明: 设设G1是是GM1 M2的的1个连通分支个连通分支, vV(G1), 1 dG1(v)=dGM1 M2(v)2, 即即dG1(v)=1或或2. 所以所以G1是交错圈或交错路径是交错圈或交错路径. #最大匹配n定理定理13.8: 设设M是是G中匹配中匹配, 是是M的可增广路径的可增广路径, 则则M=M E()也是也是G中匹配中匹配, 且且|M|=|M|+1n证明证明: 显然显然M是匹配是匹配. |M|=|M E()|=|M-E()|+|E()-M|=|M|+1.#最大匹配n定理定理13.9(Berge,1

20、957): M是是G中最大匹配中最大匹配G中无中无M可增广路径可增广路径n证明证明: ()(反证反证)定理定理13.8. ( )设设M1是是G的最大匹配的最大匹配, H=GM1 M. 若若H , H的连通分支是交错圈或交错路径的连通分支是交错圈或交错路径. M和和M1都无可增广路径都无可增广路径, 所以所以|M|=|M1|.#二部图的匹配n完备匹配完备匹配n充要条件充要条件: Hall条件条件(相异性条件相异性条件)n充分条件充分条件: t条件条件nk正则二部图正则二部图: 有有k个边个边不重不重(?)完美匹配完美匹配n无孤立点二部图无孤立点二部图: 0= 1完备匹配(complete mat

21、ching)nG=是是二部图二部图, |V1|V2|n完备匹配完备匹配: |M|=|V1|n Hall条件条件: SV1, |S|N(S)|, 其中其中N(S) = u | vS,(v,u)E = UvS(v)nt(1)条件条件: v V1, d(v)t; vV2, d(v)tn t条件条件 完备匹配完备匹配 Hall条件条件Hall定理(证明)n定理定理13.11(Hall,1935): 二部图二部图G有完备匹配有完备匹配 G满满足足Hall条件条件(|S|N(S)|)n证明证明:()显然显然. ( )(反证反证)设设M是是G中一个最大匹配中一个最大匹配,但不是完备匹但不是完备匹配配,则则

22、vx V1是是M的非饱和点的非饱和点,且且 e E-M与与vx关联关联(否否则则vx是孤立点是孤立点),且且(vx)中结点均是饱和点中结点均是饱和点(否则否则, vy (vx)是非饱和点是非饱和点,则则M (vx. vy)是是G中的匹配中的匹配,与与M是最大匹配矛盾是最大匹配矛盾).Hall定理(证明)n证明证明(续续):从从vx出发构造所有极长交错路径出发构造所有极长交错路径,由定理由定理13.9知知,这些交错路径都不是可增广的这些交错路径都不是可增广的,即每条交错路即每条交错路径以饱和点结束径以饱和点结束.令令 S=v|v V1且且v在在vx出发的交错路径上出发的交错路径上 T=v|v V

23、2且且v在在vx出发的交错路径上出发的交错路径上 各交错路径的始点和终点都在各交错路径的始点和终点都在S中中.(假设终点在假设终点在T中中,则则终点必定是非饱和点终点必定是非饱和点,与最大匹配矛盾与最大匹配矛盾) 所以所以|S|=|T|+1.T=N(S),|S|N(S),矛盾矛盾.vxeHall定理(证明?)n定理定理13.11(Hall,1935): 二部图二部图G有完备匹配有完备匹配 G满满足足Hall条件条件(|S|N(S)|)n证明证明:()显然显然. ( )(反证反证)设设G=是满足条件的是满足条件的极小极小子图子图, 则存在则存在a1,a2V1,xV2, (a1,x),(a2,x)

24、E. 删除删除(ai,x)将将破坏条件破坏条件, 则存在则存在A1,A2V1, aiAi, 在在Ai中只有中只有ai与与x相邻相邻, |(Ai)|=| Ai |.Hall定理(证明?)n证明证明:( )(续续) |(A1)(A2)| |(A1-a1)(A2-a2)|+1 |(A1A2)|+1|A1A2|+1. |(A1A2)|=|(A1)(A2)| = |(A1)|+|(A2)|-|(A1)(A2)| |A1|+|A2|-(|A1A2|+1)=|A1A2|-1, 矛盾矛盾!#t条件n定理定理13.12: 设设G=是二部图是二部图,若若V1中每个顶中每个顶点点至少至少关联关联t(t1)条边条边,

25、而而V2中每个顶点中每个顶点至多至多关联关联t条条边边,则则G中存在完备匹配中存在完备匹配n证明证明: V1中任意中任意k个顶点至少关联个顶点至少关联kt条边条边,这这kt条边至条边至少关联少关联V2中中k个顶点个顶点,即相异性条件成立即相异性条件成立. #例n(1) 满足满足t(=3)条件条件n(2) 满足满足Hall条件条件n(3) 无完备匹配无完备匹配(1)(2)(3)k正则二部图n定理定理13.13: 设设G=是是k正则二部图正则二部图,则则G中存中存在在k个边不重的完美匹配个边不重的完美匹配n证明证明: G满足满足t=k的的t条件条件, 所以有完备匹配所以有完备匹配M1,又又|V1|

26、=|V2|, 所以完备匹配就是完美匹配所以完备匹配就是完美匹配. G-M1是是k-1正正则二部图则二部图,又有完美匹配又有完美匹配M2, G-M1-M2是是k-2正则二部正则二部图图, , 一共可得一共可得k个完美匹配个完美匹配, 显然这些匹配是边不显然这些匹配是边不重的重的. #无孤立点二部图n定理定理13.14:设设G=是无孤立点二部图是无孤立点二部图,则则 0= 1n证明证明:设设M是最大匹配是最大匹配. X是是V1非饱和点集非饱和点集. S=uV1|vX,从从v到到u有交错路径有交错路径. T=uV2|vX,有有v到到u交错路径交错路径V2-X. 令令N=(V1-S)T是点覆盖是点覆盖

27、,|N|=|M|, 由定理由定理13.6知知N是是最小覆盖最小覆盖. #完美匹配n完美匹配完美匹配: 没有非饱和点的匹配没有非饱和点的匹配e1e2e3e4e5e6e7e8e1e2e3e4e5e6e7e8e1e2e3e4e5e6e7e8完美匹配n定理定理13.10(Tutte,1947): G有完美匹配有完美匹配 VV(G), p奇奇(G-V)|V|.n说明说明: p奇奇是奇数阶连通分支数是奇数阶连通分支数n证明证明: ()设设M是是G的完美匹配的完美匹配, G1是是G-V的奇阶连的奇阶连通分支通分支, 则则u1V(G1), v1V,(u1,v1)M, 所以所以p奇奇(G-V)|V|.完美匹配n证明证明: ( ) (对对G阶数归纳阶数归纳) 取取V= ,得得G是偶阶是偶阶. 取取V=u,得得G-u恰有恰有1个奇阶连通分支个奇阶连通分支. 设设S0V是使得是使得p奇奇(G-S0)=|S0|=s的的最大最大集合集合, C1,C2, Cs是是G-S0所有奇阶连通分支所有奇阶连通分支, D1,D2, Dt是是G-S0所有偶阶连通分支所有偶阶连通分支.完美匹配n证明证明: ( ) (1) 每个每个Di内部有完美匹配内部有完美匹配. SV(Di), p奇奇