独立集(例) y0,{vV4.{V1,v3V53,P0=3 《集合论与图论》第26讲
《集合论与图论》第26讲 6 独立集(例) {v0}, {v1,v4}, {v1,v3,v5}, β0=3 v0 v1 v2
定理132 婚定理132:无向图G无孤立点,是极大独 立集,则γ也是极小支配集 证明:V是极大独立集,则∨也是支配 集(反证:否则,孔u∈VV",Wv∈V, u,)∈E,V句还是独立集,矛盾) √是极小支配集(反证:否则,彐u∈V,V ↓是支配集,则彐v∈V,(V)EE,与V是 独立集相矛盾)# 《集合论与图论》第26讲
《集合论与图论》第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*是 独立集相矛盾.) #
定理132(讨论) 秦定理132:(无孤立点图)极大独立集是极 小支配集 逆命题不成立 反例:{23是极小支配集但不是独立集, 更不是极大独立集 v2 3 《集合论与图论》第26讲
《集合论与图论》第26讲 8 定理13.2(讨论) 定理13.2: (无孤立点图)极大独立集是极 小支配集 逆命题不成立 反例: {v2,v3}是极小支配集,但不是独立集, 更不是极大独立集 v1 v2 v3 v4
点覆盖( ertex cover) 无向图G=<V,E>,V≌V 点覆盖:eeE→ V(VEVAV关联e) 或ve∈E,丑VeV,v关联e 癱极小点覆盖:∨是点覆盖,其真子集都不 静最小点覆盖:||最小的点覆盖 点覆盖数:(G=V,V是最小点覆盖 《集合论与图论》第26讲
《集合论与图论》第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*是最小点覆盖
点覆盖例) {vo1V3,V5,{V1V23,V46x0=4 《集合论与图论》第26讲
《集合论与图论》第26讲 10 点覆盖(例) {v0,v1,v3,v5}, {v1,v2,v3,v4,v5,v6}, α0=4 v0 v1 v2 v3 v5