例13.1 例13.1:求全体极小支配集极小点覆盖, 极大独立集 解:(1)极小支配集 ∏,、V+∑ V∈V u∈I() ( a+b)(b+++d)(c+b+d)(d+Ctb) aC+ad+b.(幂等:a+a=a,aoa=a,逻辑加乘) ac{d}{是全体极小支配集7=1 《集合论与图论》第26讲 16
《集合论与图论》第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
例131(续) 婚例13.1:求全体极小支配集极小点覆盖, 极大独立集 解:(2极小点覆盖 (u, vEE(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}是全体极小点覆 盖.Cn=2 《集合论与图论》第26讲
《集合论与图论》第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
例131(续) 例13.1:求全体极小支配集极小点覆盖, 极大独立集 解:(3极大独立集 G无孤立点,V*是极小点覆盖 ∨√是极大独立集 {bc{b,d}{ac,d}是全体极小点覆盖, ad{ac{b是全体极大独立集.=2.# 《集合论与图论》第26讲 8
《集合论与图论》第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