《第25讲 支配,覆盖,独立,匹配 北京大学计算机系离散数学讲义(ppt版)》由会员分享，可在线阅读，更多相关《第25讲 支配,覆盖,独立,匹配 北京大学计算机系离散数学讲义(ppt版)（52页珍藏版）》请在金锄头文库上搜索。
1、2017/7/30,集合论与图论第26讲,1,第25讲 支配,覆盖,独立,匹配,支配集,独立集,点覆盖,团边覆盖, 边独立集(匹配)最大匹配, Berge定理完备匹配, Hall条件, t条件完美匹配, Tutte定理,2017/7/30,集合论与图论第26讲,2,支配集(dominating set),无向图G=, V*V支配集: u(uV-V*v(vV*(u,v)E) 或 uV-V*, vV*, uEv 极小支配集: V*是支配集, 其真子集都不是最小支配集: |V*|最小的支配集支配数: 0(G)=|V*|, V*是最小支配集,2017/7/30,集合论与图论第26讲,3,支配集(例),
2、星形图Sn: v0,v1,v2,vn-1, 0(Sn)=1轮图Wn: v0,v1,v3,v5,vn-2, 0(Wn)=1,v0,v1,v2,v3,v5,v4,2017/7/30,集合论与图论第26讲,4,定理13.1,定理13.1: 无向图G无孤立点,V1*是极小支配集,则存在V2*也是极小支配集,且V1*V2*=.证明: V1*是极小支配集,则V-V1*也是支配集.(反证: 否则, uV1*, vV-V1*, (u,v)E, V1*-u还是支配集,矛盾.) V-V1*是支配集,则V-V1*中有子集是极小支配集,设为V2*. 则V1*V2*=. #,2017/7/30,集合论与图论第26讲,5
3、,独立集(independent set),无向图G=, V*V独立集: u,vV*, (u,v)E极大独立集: V*是独立集, 其真母集都不是最大独立集: |V*|最大的独立集独立数: 0(G)=|V*|, V*是最大独立集,2017/7/30,集合论与图论第26讲,6,独立集(例),v0, v1,v4, v1,v3,v5, 0=3,v0,v1,v2,2017/7/30,集合论与图论第26讲,7,定理13.2,定理13.2: 无向图G无孤立点,V*是极大独立集,则V*也是极小支配集.证明: V*是极大独立集,则V*也是支配集.(反证: 否则, uV-V*, vV*, (u,v)E, V*u还
4、是独立集,矛盾.) V*是极小支配集(反证: 否则, uV*, V*-u是支配集, 则vV*, (u,v)E, 与V*是独立集相矛盾.) #,2017/7/30,集合论与图论第26讲,8,定理13.2(讨论),定理13.2: (无孤立点图)极大独立集是极小支配集逆命题不成立反例: v2,v3是极小支配集,但不是独立集, 更不是极大独立集,v1,v2,v3,v4,2017/7/30,集合论与图论第26讲,9,点覆盖(vertex cover),无向图G=, V*V点覆盖: e(eEv(vV*v关联e) 或 eE, vV*, v关联e极小点覆盖: V*是点覆盖, 其真子集都不是最小点覆盖: |V*
5、|最小的点覆盖点覆盖数: 0(G)=|V*|, V*是最小点覆盖,2017/7/30,集合论与图论第26讲,10,点覆盖(例),v0,v1,v3,v5, v1,v2,v3,v4,v5,v6, 0=4,v0,v1,v2,v3,v5,2017/7/30,集合论与图论第26讲,11,讨论,(连通图)点覆盖是支配集极小点覆盖不一定是极小支配集.反例: v0,v1, v3,v5是极小点覆盖, v1,v3,v5是极小支配集支配集不一定是点覆盖. 反例: v1,v4是支配集,不是点覆盖,v0,v1,v2,v3,v5,2017/7/30,集合论与图论第26讲,12,定理13.3,定理13.3: 无向图G无孤立
6、点, V*V, V*是点覆盖 V-V*是独立集.证明: () (反证) 否则, u,vV-V*, (u,v)E, V*不是点覆盖,矛盾. () V-V*是独立集, (u,v)E, uV-V* vV-V*, uV* vV*, V*是点覆盖. #推论: 无向图G无孤立点, V*是极(最)小点覆盖V-V*是极(最)大独立集.0+0=n.#,2017/7/30,集合论与图论第26讲,13,团(clique),无向图G=, V*V团: GV*是完全子图极大团: V*是团, 其真母集都不是最大团: |V*|最大的团团数: 0(G)=|V*|, V*是最大团,2017/7/30,集合论与图论第26讲,14,
7、团(例),v0,v1,v2, v1,v2, v1, 0=3,v0,v1,v2,2017/7/30,集合论与图论第26讲,15,定理13.4,定理13.4: 无向图G, V*是G的团 V*是G的独立集. #推论: 无向图G, V*是G的极(最)大团V*是G的极(最)大独立集. 0(G)=0(G). #总结: 0+0=n(无孤立点). 0(G)=0(G). 所以 0, 0, 0三者互相确定, 但都是难解的(目前都没有多项式时间算法),2017/7/30,集合论与图论第26讲,16,例13.1,例13.1: 求全体极小支配集,极小点覆盖,极大独立集解: (1)极小支配集. vV(v+u(v)u)=(
8、a+b)(b+a+c+d)(c+b+d)(d+c+b)=ac+ad+b. (幂等: a+a=a,aa=a, 逻辑加乘) a,c, a,d, b是全体极小支配集. 0=1.,a,b,c,d,2017/7/30,集合论与图论第26讲,17,例13.1(续),例13.1: 求全体极小支配集,极小点覆盖,极大独立集解: (2)极小点覆盖. (u,v)E(u+v)=(a+b)(b+c)(b+d)(c+d)=bc+bd+acd. (幂等: a+a=a,aa=a, 逻辑加乘) b,c, b,d, a,c,d是全体极小点覆盖. 0=2.,a,b,c,d,2017/7/30,集合论与图论第26讲,18,例13.
9、1(续),例13.1: 求全体极小支配集,极小点覆盖,极大独立集解: (3)极大独立集. G无孤立点, V*是极小点覆盖 V-V*是极大独立集. b,c,b,d,a,c,d是全体极小点覆盖, a,d,a,c,b是全体极大独立集. 0=2. #,a,b,c,d,2017/7/30,集合论与图论第26讲,19,边覆盖(edge cover),无向图G=, E*E边覆盖: vE, eE*, e关联v极小边覆盖: E*是边覆盖, 其真子集都不是最小边覆盖: |E*|最小的边覆盖边覆盖数: 1(G)=|E*|, E*是最小点覆盖,2017/7/30,集合论与图论第26讲,20,边覆盖(例),e2,e3,
10、e6, e2,e3,e7, 1=3,e1,e2,e3,e4,e6,e7,e5,e1,e2,e3,e4,e6,e7,e5,e1,e2,e3,e4,e6,e7,e5,2017/7/30,集合论与图论第26讲,21,匹配(matching),无向图G=, E*E匹配(边独立集): e,fE*, e,f不相邻极大匹配: E*是匹配, 其真母集都不是最大匹配: |E*|最大的匹配匹配数: 1(G)=|E*|, E*是最大匹配,2017/7/30,集合论与图论第26讲,22,匹配(例),e1,e7, e1,e4, e5, 1=2,e1,e2,e3,e4,e6,e7,e5,e1,e2,e3,e4,e6,e7
11、,e5,e1,e2,e3,e4,e6,e7,e5,e1,e2,e3,e4,e6,e7,e5,2017/7/30,集合论与图论第26讲,23,饱和点,交错路径,增广路径,设M是G中匹配饱和点: v与M中边关联非饱和点: v不与M中边关联交错路径: 在M和E-M中交替取边的路径可增广交错路径: 两端都是非饱和点的交错路径,2017/7/30,集合论与图论第26讲,24,举例,e1,e2,e3,e4,e6,e7,e5,e8,e1,e2,e3,e4,e6,e7,e5,e8,e1,e2,e3,e4,e6,e7,e5,e8,e1,e2,e3,e4,e6,e7,e5,e8,2017/7/30,集合论与图论第
12、26讲,25,定理13.5,定理13.5: 无向图G无孤立点,(1) 设M是最大匹配, 非饱和点v, 取v关联的一边, 组成边集N, 则W=MN是最小边覆盖(2) 设W1是最小边覆盖, 若W1中有相邻边, 就删除其中一边, 直到无相邻边为止,设删除的边组成边集N1, 则M1=W1-N1是最大匹配(3) 1+1=n,2017/7/30,集合论与图论第26讲,26,定理13.5(证明),证明: M是最大匹配, |M|=1, |N|=n-21, 1|W|=|M|+|N|=n-1.(*) W1是最小边覆盖, |W1|=1, 删除1边恰产生1个非饱和点, |N1|=|W1|-|M1|=“删除边数”=“M
13、1的非饱和点数”=n-2|M1|, 1=|W1|=n-|M1|n-1.(*) 由(*)(*), n1+1n, 所以1+1=n. 由(*), |W|=1, W是最小边覆盖. 由(*), |M1|=1, M1是最大匹配. #,2017/7/30,集合论与图论第26讲,27,定理13.6,定理13.6: 无向图G无孤立点, M是匹配, N是点覆盖, Y是独立集, W是边覆盖, 则 (1) |M|N|, (2) |Y|W|, (3) 等号成立时, M是最大匹配, N是最小点覆盖, Y是最大独立集, W是最小边覆盖证明: (1) M中边不相邻, 至少需要|M|个点才能覆盖M. (2) Y中顶点不相邻, 至少需要|Y|条边才能覆盖Y. |M|=|N|说明|M|达到最大值, |N|达到最小值. |Y|=|W|类似. #,2017/7/30,集合论与图论第26讲,28,推论,推论: 无向图G无孤立点, 则10, 01. #Kr,s: 1=0=minr,s, 0=1=maxr,s,总结: 无向图G无孤立点, 则 10(0,?) 0=01. 0+0=n, 1+1=n,
