支配集,點獨立集,點覆蓋集,團邊覆蓋, 邊獨立集(匹配)

1、 Peking University1n支配集,點獨立集,點覆蓋集,團n邊覆蓋, 邊獨立集(匹配)第13章 Peking University2支配集(dominating set)n無向圖G=, V*Vn支配集: u(uV-V*v(vV*(u,v)E) 或 uV-V*, vV*, uEv n極小支配集: V*是支配集, 其真子集都不是n最小支配集: |V*|最小的支配集n支配數(shù): 0(G)=|V*|, V*是最小支配集 Peking University3支配集(例)n星形圖Sn: v0,v1,v2,vn-1, 0(Sn)=1n輪圖Wn: v0,v1,v3,v5,vn-2, 0(Wn)=1v

2、0v1v2v3v5v4 Peking University4定理13.1n定理13.1: 無向圖G無孤立點,V1*是極小支配集,則存在V2*也是極小支配集,且V1*V2*=.n證明: V1*是極小支配集,則V-V1*也是支配集.(反證: 否則, uV1*, vV-V1*, (u,v)E, V1*-u還是支配集,矛盾.) V-V1*是支配集,則V-V1*中有子集是極小支配集,設(shè)為V2*. 則V1*V2*=. # Peking University5獨立集(independent set)n無向圖G=, V*Vn獨立集: u,vV*, (u,v)En極大獨立集: V*是獨立集, 再加入任何頂點都不

3、再是獨立集n最大獨立集: |V*|最大的獨立集n獨立數(shù): 0(G)=|V*|, V*是最大獨立集 Peking University6獨立集(例)nv0, v1,v4, v1,v3,v5, 0=3v0v1v2v0v1v2v3v4v5v6v0v1v2v3v4v5v6 Peking University7定理13.2n定理13.2: 無向圖G無孤立點,V*是極大獨立集,則V*也是極小支配集.n證明: V*是極大獨立集,則V*也是支配集.(反證: 否則, uV-V*, vV*, (u,v)E, V*u還是獨立集,矛盾.) V*是極小支配集(反證: 否則, uV*, V*-u是支配集, 則vV*, (

4、u,v)E, 與V*是獨立集相矛盾.) # Peking University8定理13.2n定理13.2: 極大獨立集是極小支配集n逆命題不成立n反例: v2,v3是極小支配集,但不是獨立集, 更不是極大獨立集n00n極大獨立集小于最大獨立集n極小支配集大于最小支配集v1v2v3v4 Peking University9點覆蓋(vertex cover)n無向圖G=, V*Vn點覆蓋: e(eEv(vV*v關(guān)聯(lián)e) 或 eE, vV*, v關(guān)聯(lián)en極小點覆蓋: V*是點覆蓋, 其真子集都不是n最小點覆蓋: |V*|最小的點覆蓋n點覆蓋數(shù): 0(G)=|V*|, V*是最小點覆蓋 Peking

5、 University10點覆蓋(例)nv0,v1,v3,v5, v1,v2,v3,v4,v5,v6, 0=4v0v1v2v3v5 Peking University11討論n(連通圖)點覆蓋是支配集n極小點覆蓋不一定是極小支配集.例: v0,v1, v3,v5是極小點覆蓋, v1,v3,v5是極小支配集n支配集不一定是點覆蓋. 反例: v1,v4是支配集,不是點覆蓋 v0v1v2v3v5 Peking University12定理13.3n定理13.3: 無向圖G無孤立點, V*V, V*是點覆蓋 V-V*是獨立集.n證明: () (反證) 否則, u,vV-V*, (u,v)E, V*不是

6、點覆蓋,矛盾. () V-V*是獨立集, (u,v)E, 兩個點不能同時在V-V*中，uV-V* vV-V*, uV* vV*, V*是點覆蓋. # Peking University13n推論: 無向圖G無孤立點, V*是極(最)小點覆蓋V-V*是極(最)大獨立集.0+0=n.# Peking University14團(clique)n無向圖G=, V*Vn團: GV*是完全子圖n極大團: V*是團, 加入任何頂點不是團n最大團: |V*|最大的團n團數(shù): 0(G)=|V*|, V*是最大團 Peking University15團(例)nv0,v1,v2, v1,v2, v1, 0=3v

7、0v1v2 Peking University16定理13.4n定理13.4: 無向圖G, V*是G的團 V*是G的獨立集. #n推論: 無向圖G, V*是G的極(最)大團V*是G的極(最)大獨立集. 0(G)=0(G). # Peking University170 0 0 0n極大獨立集是極小支配集n00 n0+0=n (無孤立點).n 0(G)=0(G). n 0, 0, 0三者互相確定, 但都是難解的(目前都沒有多項式時間算法) Peking University18例13.1n例13.1: 求全體極小支配集,極小點覆蓋,極大獨立集n解: (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.abcd Peking University19例13.1(續(xù))n例13.1: 求全體極小支配集,極小點覆蓋,極大獨立集n解: (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. abcd Peking University20例13.1(續(xù))n例13.1: 求全體極

9、小支配集,極小點覆蓋,極大獨立集n解: (3)極大獨立集. G無孤立點, V*是極小點覆蓋 V-V*是極大獨立集. b,c,b,d,a,c,d是全體極小點覆蓋, a,d,a,c,b是全體極大獨立集. 0=2. #abcd Peking University21邊覆蓋(edge cover)n無向圖G=, E*En邊覆蓋: vE, eE*, e關(guān)聯(lián)vn極小邊覆蓋: E*是邊覆蓋, 其真子集都不是n最小邊覆蓋: |E*|最小的邊覆蓋n邊覆蓋數(shù): 1(G)=|E*|, E*是最小點覆蓋 Peking University22邊覆蓋(例)ne2,e3,e6, e2,e3,e7, 1=3e1e2e3e4

10、e6e7e5e1e2e3e4e6e7e5e1e2e3e4e6e7e5 Peking University23匹配(matching)n無向圖G=, E*En匹配(邊獨立集): e,fE*, e,f不相鄰n極大匹配: E*是匹配, 添加任何邊都不是n最大匹配: |E*|最大的匹配n匹配數(shù): 1(G)=|E*|, E*是最大匹配 Peking University24匹配(例)ne1,e7, e1,e4,e2,e6 e5, n1=2e1e2e3e4e6e7e5e1e2e3e4e6e7e5e1e2e3e4e6e7e5e1e2e3e4e6e7e5 Peking University25飽和點,交錯路徑

11、,增廣路徑n設(shè)M是G中匹配n飽和點: v與M中邊關(guān)聯(lián)n非飽和點: v不與M中邊關(guān)聯(lián)n交錯路徑: 在M和E-M中交替取邊的路徑n可增廣交錯路徑: 兩端都是非飽和點的交錯路徑 Peking University26舉例e1e2e3e4e6e7e5e8e1e2e3e4e6e7e5e8e1e2e3e4e6e7e5e8e1e2e3e4e6e7e5e8 Peking University27定理13.5n定理13.5: 無向圖G無孤立點,(1) 設(shè)M是最大匹配, 非飽和點v, 取v關(guān)聯(lián)的一邊, 組成邊集N, 則W=MN是最小邊覆蓋(2) 設(shè)W1是最小邊覆蓋, 若W1中有相鄰邊, 就刪除其中一邊, 直到無相

12、鄰邊為止,設(shè)刪除的邊組成邊集N1, 則M1=W1-N1是最大匹配(3) 1+1=n Peking University28定理13.5(證明)n證明: M是最大匹配, |M|=1, |N|=n-21, 1|W|=|M|+|N|=n-1.(*) W1是最小邊覆蓋, |W1|=1, 因為W1中任意一條邊的兩個端點不可能都與其它邊相關(guān)聯(lián)，刪除1邊恰產(chǎn)生1個非飽和點, |N1|=|W1|-|M1|=“刪除邊數(shù)”=“M1的非飽和點數(shù)”=n-2|M1|, 1=|W1|=n-|M1|n-1.(*) 由(*)(*), n1+1n, 所以1+1=n. 由(*), |W|=1, W是最小邊覆蓋. 由(*), |M

13、1|=1, M1是最大匹配. #e1e2e3e4e6e7e5 Peking University29推論n無向圖G無孤立點, M是匹配, W是邊覆蓋, 則|M| |W| 等號成立時, M是完美匹配, W是最小邊覆蓋.n證: 由定理13.5證明(1)可知1 1, 于是|M| 1 1 |W|,當(dāng)|M|=|W| 時, 得|M| = 1 = 1 = |W|, 因而M是最大匹配, W是最小邊覆蓋, 再由定理13.5(3)可知1+1= 21= n, 所以M是完美匹配. # Peking University30定理13.6n定理13.6: 無向圖G無孤立點, M是匹配, N是點覆蓋, Y是點獨立集, W是

14、邊覆蓋, 則 (1) |M|N|, (2) |Y|W|, (3) 等號成立時, M是最大匹配, N是最小點覆蓋, Y是最大獨立集, W是最小邊覆蓋n證明: (1) M中邊不相鄰, 至少需要|M|個點才能覆蓋M. (2) Y中頂點不相鄰, 至少需要|Y|條邊才能覆蓋Y. |M|=|N|說明|M|達到最大值, |N|達到最小值. |Y|=|W|類似. # Peking University31推論n推論: 無向圖G無孤立點, 則1 0, 0 1. #n完全二部圖Kr ,s: 1=0=minr,s,0=1=maxr,s, Peking University32完美匹配, 完備匹配n完美匹配(perf

15、ect matching): 沒有非飽和點的匹配n完備匹配(complete matching) : G=是二部圖, |V1|V2|, |M|=|V1|n求最小邊覆蓋, 最大匹配, 完美匹配, 都是易解的(有多項式時間算法) Peking University33最大匹配n定理13.7: 設(shè)M1,M2是G中2個不同匹配,則GM1M2的每個連通分支是M1,M2中的邊組成的交錯圈或交錯路徑n證明: 設(shè)G1是GM1M2的1個連通分支, vV(G1), 0dG1(v)=dGM1M2(v)2, 即 dG1(v)=1或2. 所以G1是交錯圈或交錯路徑. # Peking University34最大匹配n定理13.8: 設(shè)M是G中匹配, 是M的可增廣路徑, 則M=ME()也是G中匹配, 且 |M|=|M|+1n證明: 顯然M是匹配.由于上非M中的邊比M中的邊多一條 |M|=|ME()|=|M-E()|+|E()-M|=|M|+1. # Peking University35最大匹配n定理13.9(Berge,1957): M是G中最大匹配G中無M可增廣路徑n證明: