《集合论与图论》第26讲1 第25讲支配,覆盖,独立,匹配 ?支配集,独立集,点覆盖,团 ?边覆盖, 边独立集(匹配) ?最大匹配, Berge定理 ?完备匹配, Hall条件, t条件 ?完美匹配, Tutte定理 《集合论与图论》第26讲2 支配集(dominating set) ?无向图G=<V,E>, V*?V ?支配集: ?u(u∈V-V*→?v(v∈V*∧(u,v)∈E)) 或?u∈V-V*, ?v∈V*, uEv ?极小支配集: V*是支配集, 其真子集都不 是 ?最小支配集: |V*|最小的支配集 ?支配数: γ 0 (G)=|V*|, V*是最小支配集 《集合论与图论》第26讲3 支配集(例) ?星形图S n : {v 0 },{v 1 ,v 2 ,…,v n-1 }, γ 0 (S n )=1 ?轮图W n : {v 0 },{v 1 ,v 3 ,v 5 …,v n-2 }, γ 0 (W n )=1 v 0 v 1 v 2 v 3 v 5 v 4 《集合论与图论》第26讲4 定理13.1 ?定理13.1: 无向图G无孤立点,V 1 *是极小 支配集,则存在V 2 *也是极小支配集,且 V 1 *∩V 2 *=?. ?证明: V 1 *是极小支配集,则V-V 1 *也是支配 集.(反证: 否则, ?u∈V 1 *, ?v∈V-V 1 *, (u,v)?E, V 1 *-{u}还是支配集,矛盾.) V-V 1 *是支配集,则V-V 1 *中有子集是极小 支配集,设为V 2 *. 则V 1 *∩V 2 *=?. # 《集合论与图论》第26讲5 独立集(independent set) ?无向图G=<V,E>, V*?V ?独立集: ?u,v∈V*, (u,v)?E ?极大独立集: V*是独立集, 其真母集都不 是 ?最大独立集: |V*|最大的独立集 ?独立数: β 0 (G)=|V*|, V*是最大独立集 《集合论与图论》第26讲6 独立集(例) ?{v 0 }, {v 1 ,v 4 }, {v 1 ,v 3 ,v 5 }, β 0 =3 v 0 v 1 v 2 《集合论与图论》第26讲7 定理13.2 ?定理13.2: 无向图G无孤立点,V*是极大独 立集,则V*也是极小支配集. ?证明: V*是极大独立集,则V*也是支配 集.(反证: 否则, ?u∈V-V*, ?v∈V*, (u,v)?E, V*∪{u}还是独立集,矛盾.) V*是极小支配集(反证: 否则, ?u∈V*, V*- {u}是支配集,则?v∈V*, (u,v)∈E,与V*是 独立集相矛盾.) # 《集合论与图论》第26讲8 定理13.2(讨论) ?定理13.2: (无孤立点图)极大独立集是极 小支配集 ?逆命题不成立 ?反例: {v 2 ,v 3 }是极小支配集,但不是独立集, 更不是极大独立集 v 1 v 2 v 3 v 4 《集合论与图论》第26讲9 点覆盖(vertex cover) ?无向图G=<V,E>, V*?V ?点覆盖: ?e(e∈E→?v(v∈V*∧v关联e)) 或?e∈E, ?v∈V*, v关联e ?极小点覆盖: V*是点覆盖, 其真子集都不 是 ?最小点覆盖: |V*|最小的点覆盖 ?点覆盖数: α 0 (G)=|V*|, V*是最小点覆盖 《集合论与图论》第26讲10 点覆盖(例) ?{v 0 ,v 1 ,v 3 ,v 5 }, {v 1 ,v 2 ,v 3 ,v 4 ,v 5 ,v 6 }, α 0 =4 v 0 v 1 v 2 v 3 v 5 《集合论与图论》第26讲11 讨论 ?(连通图)点覆盖是支配集 ?极小点覆盖不一定是极小支配集.反例: {v 0 ,v 1 , v 3 ,v 5 }是极小点覆盖, {v 1 ,v 3 ,v 5 }是极 小支配集 ?支配集不一定是点覆盖. 反例: {v 1 ,v 4 }是支 配集,不是点覆盖 v 0 v 1 v 2 v 3 v 5 《集合论与图论》第26讲12 定理13.3 ?定理13.3: 无向图G无孤立点, V*?V, V*是点覆盖? V-V*是独立集. ?证明: (?) (反证) 否则, ?u,v∈V-V*, (u,v)∈E, V*不是点覆盖,矛盾. (?)V-V*是独立集, ?(u,v)∈E, u?V-V*∨ v?V-V*, u∈V* ∨ v∈V*, V*是点覆盖. # ?推论: 无向图G无孤立点, V*是极(最)小点 覆盖?V-V*是极(最)大独立集.α 0 +β 0 =n.# 《集合论与图论》第26讲13 团(clique) ?无向图G=<V,E>, V*?V ?团: G[V*]是完全子图 ?极大团: V*是团, 其真母集都不是 ?最大团: |V*|最大的团 ?团数: ν 0 (G)=|V*|, V*是最大团 《集合论与图论》第26讲14 团(例) ?{v 0 ,v 1 ,v 2 }, {v 1 ,v 2 }, {v 1 }, ν 0 =3 v 0 v 1 v 2 《集合论与图论》第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 三者互相确定, 但都是难解 的(目前都没有多项式时间算法) 《集合论与图论》第26讲16 例13.1 ?例13.1: 求全体极小支配集,极小点覆盖, 极大独立集 ?解: (1)极小支配集. Π v∈V (v+Σ u∈Γ(v) u) =(a+b)(b+a+c+d)(c+b+d)(d+c+b) =ac+ad+b. (幂等: a+a=a,a?a=a, 逻辑加乘) {a,c}, {a,d}, {b}是全体极小支配集. γ 0 =1. a b c d 《集合论与图论》第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,a?a=a, 逻辑加 乘) {b,c}, {b,d}, {a,c,d}是全体极小点覆 盖. α 0 =2. a b c d 《集合论与图论》第26讲18 例13.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 《集合论与图论》第26讲19 边覆盖(edge cover) ?无向图G=<V,E>, E*?E ?边覆盖: ?v∈E, ?e∈E*, e关联v ?极小边覆盖: E*是边覆盖, 其真子集都不 是 ?最小边覆盖: |E*|最小的边覆盖 ?边覆盖数: α 1 (G)=|E*|, E*是最小点覆盖 《集合论与图论》第26讲20 边覆盖(例) ?{e 2 ,e 3 ,e 6 }, {e 2 ,e 3 ,e 7 }, α 1 =3 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 1 e 2 e 3 e 4 e 6 e 7 e 5 《集合论与图论》第26讲21 匹配(matching) ?无向图G=<V,E>, E*?E ?匹配(边独立集): ?e,f∈E*, e,f不相邻 ?极大匹配: E*是匹配, 其真母集都不是 ?最大匹配: |E*|最大的匹配 ?匹配数: β 1 (G)=|E*|, E*是最大匹配 《集合论与图论》第26讲22 匹配(例) ?{e 1 ,e 7 }, {e 1 ,e 4 }, {e 5 }, ?β 1 =2 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 1 e 2 e 3 e 4 e 6 e 7 e 5 《集合论与图论》第26讲23 饱和点,交错路径,增广路径 ?设M是G中匹配 ?饱和点: v与M中边关联 ?非饱和点: v不与M中边关联 ?交错路径: 在M和E-M中交替取边的路径 ?可增广交错路径: 两端都是非饱和点的交 错路径 《集合论与图论》第26讲24 举例 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 《集合论与图论》第26讲25 定理13.5 ?定理13.5: 无向图G无孤立点, (1) 设M是最大匹配, ?非饱和点v, 取v关联 的一边, 组成边集N, 则W=M∪N是最小边 覆盖 (2) 设W 1 是最小边覆盖, 若W 1 中有相邻边, 就删除其中一边, 直到无相邻边为止,设 删除的边组成边集N 1 , 则M 1 =W 1 -N 1 是最 大匹配 (3) α 1 +β 1 =n 《集合论与图论》第26讲26 定理13.5(证明) ?证明: M是最大匹配, |M|=β 1 , |N|=n-2β 1 , α 1 ≤|W|=|M|+|N|=n-β 1 .(*) W 1 是最小边覆 盖, |W 1 |=α 1 , 删除1边恰产生1个非饱和点, |N 1 |=|W 1 |-|M 1 |=“删除边数”=“M 1 的非饱和 点数”=n-2|M 1 |, α 1 =|W 1 |=n-|M 1 |≥n-β 1 .(**) 由(*)(**), n≤α 1 +β 1 ≤n, 所以α 1 +β 1 =n. 由(*), |W|=α 1 , W是最小边覆盖. 由(**), |M 1 |=β 1 , M 1 是最大匹配. # 《集合论与图论》第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|类似. # 《集合论与图论》第26讲28 推论 ?推论: 无向图G无孤立点, 则 β 1 ≤α 0 , β 0 ≤α 1 . # ?K r,s : β 1 =α 0 =min{r,s}, β 0 =α 1 =max{r,s}, ?总结: 无向图G无孤立点, 则 β 1 ≤α 0 (≤γ 0 ,?) ν 0 =β 0 ≤α 1 . α 0 +β 0 =n, α 1 +β 1 =n, 《集合论与图论》第26讲29 完美匹配, 完备匹配 ?完美匹配(perfect matching): 没有非饱和 点的匹配 ?完备匹配(complete matching) : G=<V 1 ,V 2 ,E>是二部图, |V 1 |≤|V 2 |, |M|=|V 1 | ?求最小边覆盖, 最大匹配, 完美匹配, 都是 易解的(有多项式时间算法) 《集合论与图论》第26讲30 完美匹配(例) e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 《集合论与图论》第26讲31 最大匹配 ?定理13.7: 设M 1 ,M 2 是G中2个不同匹配,则 G[M 1 ⊕M 2 ]的每个连通分支是M 1 ,M 2 中的 边组成的交错圈或交错路径 ?证明: 设G 1 是G[M 1 ⊕M 2 ]的1个连通分支, ?v∈V(G 1 ), 0<d G1 (v)=d G[M1⊕M2] (v)≤2, 即 d G1 (v)=1或2. 所以G 1 是交错圈或交错路 径. # 《集合论与图论》第26讲32 最大匹配 ?定理13.8: 设M是G中匹配, Γ是M的可增 广路径, 则M’=M⊕E(Γ)也是G中匹配, 且 |M’|=|M|+1 ?证明: 显然M是匹配. |M’|=|M⊕E(Γ)|=|M-E(Γ)|+|E(Γ)-M|=|M|+1. # 《集合论与图论》第26讲33 最大匹配 ?定理13.9(Berge,1957): M是G中最大匹配?G中无M可增广路径 ?证明: (?)(反证)定理13.8. (?)设M 1 是G的最大匹配, H=G[M 1 ⊕M]. 若H≠?, H的连通分支是交错圈或交错路 径. M和M 1 都无可增广路径, 所以|M|=|M 1 |. # 《集合论与图论》第26讲34 二部图的匹配 ?完备匹配 ?充要条件: Hall条件(相异性条件) ?充分条件: t条件 ?k正则二部图: 有k个边不重完美匹配 ?无孤立点二部图: α 0 =β 1 《集合论与图论》第26讲35 完备匹配(complete matching) ?G=<V 1 ,V 2 ,E>是二部图, |V 1 |≤|V 2 | ?完备匹配: |M|=|V 1 | ?Hall条件: ?S?V 1 , |S|≤|N(S)|, 其中N(S) = { u | ?v∈S,(v,u)∈E } = U v∈S Γ(v) ?t(≥1)条件: ?v∈V 1 , d(v)≥t; ?v∈V 2 , d(v)≤t ?t条件? ?完备匹配? Hall条件 《集合论与图论》第26讲36 Hall定理 ?定理13.11(Hall,1935): 二部图G有完备匹 配? G满足Hall条件(|S|≤|N(S)|) ?证明:(?)显然. (?)(反证)设G=<V 1 ,V 2 ,E> 是满足条件的极小子图, 则存在a 1 ,a 2 ∈V 1 , x∈V 2 , (a 1 ,x),(a 2 ,x)∈E. 删除(a i ,x)将破坏 条件, 则存在A 1 ,A 2 ?V 1 , a i ∈A i , 在A i 中只有 a i 与x相邻, |Γ(A i )|=|A i |. 《集合论与图论》第26讲37 Hall定理 ?证明:(?)(续) |Γ(A 1 )∩Γ(A 2 )| ≥ |Γ(A 1 -{a 1 })∩Γ(A 2 -{a 2 })|+1 ≥ |Γ(A 1 ∩A 2 )|+1≥|A 1 ∩A 2 |+1. |Γ(A 1 ∪A 2 )|=|Γ(A 1 )∪Γ(A 2 )| = |Γ(A 1 )|+|Γ(A 2 )|-|Γ(A 1 )∩Γ(A 2 )| ≤ |A 1 |+|A 2 |-(|A 1 ∩A 2 |+1)=|A 1 ∪A 2 |-1, 矛盾! # 《集合论与图论》第26讲38 t条件 ?定理13.12: 设G=<V 1 ,V 2 ,E>是二部图,若 V 1 中每个顶点至少关联t(t≥1)条边,而V 2 中 每个顶点至多关联t条边,则G中存在完备 匹配 ?证明: V 1 中任意k个顶点至少关联kt条边, 这kt条边至少关联V 2 中k个顶点,即相异性 条件成立. # 《集合论与图论》第26讲39 例 ?(1) 满足t(=3)条件 ?(2) 满足Hall条件 ?(3) 无完备匹配 (1) (2) (3) 《集合论与图论》第26讲40 k正则二部图 ?定理13.13: 设G=<V 1 ,V 2 ,E>是k正则二部 图,则G中存在k个边不重的完美匹配 ?证明: G满足t=k的t条件, 所以有完备匹配 M 1 ,又|V 1 |=|V 2 |, 所以完备匹配就是完美匹 配. G-M 1 是k-1正则二部图,又有完美匹配 M 2 , G-M 1 -M 2 是k-2正则二部图, …, 一共 可得k个完美匹配, 显然这些匹配是边不 重的. # 《集合论与图论》第26讲41 无孤立点二部图 ?定理13.14:设G=<V 1 ,V 2 ,E>是无孤立点二 部图,则α 0 =β 1 ?证明:设M是最大匹配. X是V 1 非饱和点集. S={u∈V 1 |?v∈X,从v到u有交错路径}. T={u∈V 2 |?v∈X,有v到u交错路径}?V 2 -X. 令N=(V 1 -S)∪T是点覆盖,|N|=|M|, 由定理 13.6知N是最小覆盖. # 《集合论与图论》第26讲42 完美匹配 ?完美匹配: 没有非饱和点的匹配 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 e 1 e 2 e 3 e 4 e 6 e 7 e 5 e 8 《集合论与图论》第26讲43 完美匹配 ?定理13.10(Tutte,1947): G有完美匹配 ??V’?V(G), p 奇 (G-V’)≤|V’|. ?说明: p 奇 是奇数阶连通分支数 ?证明: (?)设M是G的完美匹配, G 1 是G-V’ 的奇阶连通分支, 则?u 1 ∈V(G 1 ), ?v 1 ∈V’, (u 1 ,v 1 )∈M, 所以p 奇 (G-V’)≤|V’|. 《集合论与图论》第26讲44 完美匹配 ?证明: (?) (对G阶数归纳) 取V’=?,得G是偶阶. 取V’={u},得G-{u}恰有1个奇阶连通分支. 设S 0 ?V是使得p 奇 (G-S 0 )=|S 0 |=s的最大集合, C 1 ,C 2 ,…, C s 是G-S 0 所有奇阶连通分支, D 1 ,D 2 ,…, D t 是G-S 0 所有偶阶连通分支. 《集合论与图论》第26讲45 完美匹配 ?证明: (?) (1) 每个D i 内部有完美匹配. ?S?V(D i ), p 奇 (G-S 0 )+p 奇 (D i -S) =p 奇 (G-(S 0 ∪S))≤|S 0 ∪S|=|S 0 |+|S|, 所以 p 奇 (D i -S)≤|S|, 由归纳假设, D i 内部有完美 匹配. 《集合论与图论》第26讲46 完美匹配 ?证明: (?) (2) 每个C i -{c}内部有完美匹配, 其中 c∈C i . (反证) 假设?S?V(C i -{c}), p 奇 (C i -{c}-S)) >|S|, 因两端同奇偶, 故p 奇 (C i -{c}-S))≥|S|+2. |S 0 ∪{c}∪S|=|S 0 |+1+|S|≥p 奇 (G-(S 0 ∪{c}∪S)) =p 奇 (G-S 0 )-1+p 奇 (C i -{c}-S))≥|S 0 |+1+|S|, 与S 0 的 最大性矛盾. 《集合论与图论》第26讲47 完美匹配 ?证明: (?) (3) H=G[{C 1 ,C 2 ,…, C s },S 0 ]有 完美匹配. ?A?{C 1 ,C 2 ,…,C s },令B=Γ H (A), 则|A|≤p 奇 (G-B)≤|B|, 即满足Hall条件, 所 以H有完美匹配. 于是G的完美匹配由(3)(2)(1)三部分构成. # 《集合论与图论》第26讲48 推论 ?推论: 无桥3正则图有完美匹配 ?证明: 设G-V 1 的奇阶连通分支是G i , i=1,2,…,r, |V(G i )|=n i , |[V(G i ),V 1 ]|=m i . Σ v∈V(Gi) d G (v)=3n i =2|E(G i )|+m i , m i 是奇数. 无桥, m i ≥3. p 奇 (G-V 1 )=r≤(Σ r i=1 m i )/3 ≤(Σ v∈V1 d G (v))/3=|V 1 |, 再用定理13.10. # 《集合论与图论》第26讲49 推论(说明) ?说明:无桥条件不能去掉. ?反例: p 奇 (G-{v})=3>|{v}|=1.G无完美匹配. v 《集合论与图论》第26讲50 总结 ?支配集,独立集,点覆盖,团(难解问题) ?边覆盖, 边独立集(匹配) (易解问题) ?α 0 , β 0 , γ 0 , ν 0 , α 1 , β 1 ?最大匹配, Berge定理 ?完备匹配, Hall条件, t条件 ?完美匹配, Tutte定理 《集合论与图论》第26讲51 作业(#21) ?p334, 习题十三, 3,4,5,7,8 《集合论与图论》第26讲52 期末考试 ?时间: 5月8日(周四)晚7:10-9:10 ?地点: 理教107(单学号), 201(双学号) 按学号末位分教室, 按指示就座, 带上学生证或听课证. ?答疑: 5月7日(周三)上午10:00-12:00, 晚7:00-10:00,理科1#楼1625(22)室