讨论 连通图)点覆盖是支配集 极小点覆盖不一定是极小支配集反例: {voV1,v3v5是极小点覆盖,{v1V3,V5是极 小支配集 支配集不一定是点覆盖.反例:{1,V4是支 配集,不是点覆盖 3《集合论与图论》第26讲
《集合论与图论》第26讲 11 讨论 (连通图)点覆盖是支配集 极小点覆盖不一定是极小支配集.反例: {v0,v1, v3,v5}是极小点覆盖, {v1,v3,v5}是极 小支配集 支配集不一定是点覆盖. 反例: {v1,v4}是支 配集,不是点覆盖 v0 v1 v2 v3 v5
定理133 秦定理133:无向图G无孤立点,VV, √是点覆盖◇∨是独立集. 证明:(→)(反证)否则,彐uV∈V-V u,)∈E,V不是点覆盖,矛盾 (=)VV是独立集,V(u)E,uEVV V∈V-V,u∈Wvv∈,V是点覆盖.# 壽推论:无向图G无孤立点,V是极(最)小点 覆盖<∨-V是极(最)大独立集.∞+=,# 《集合论与图论》第26讲
《集合论与图论》第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.#
团( clique) 无向图G=<V,E>,V"V 团:GⅣ]是完全子图 极大团:∨是团,其真母集都不是 最大团:N最大的团 团数:V(G=N,V是最大团 《集合论与图论》第26讲 13
《集合论与图论》第26讲 13 团(clique) 无向图G=<V,E>, V*⊆V 团: G[V*]是完全子图 极大团: V*是团, 其真母集都不是 最大团: |V*|最大的团 团数: ν0(G)=|V*|, V*是最大团
团(例) {vo1V2.{V1,V2{Vv=3 《集合论与图论》第26讲
《集合论与图论》第26讲 14 团(例) {v0,v1,v2}, {v1,v2}, {v1}, ν0=3 v0 v1 v2
定理134 婚定理134:无向图G, 是G的团∨是G的独立集.# 推论;无向图G,V是G的极(最)大团 是G的极(最)大独立集.w0(G=BG).# 总结:0+0=n(无孤立点).v0(G)=G) 所以∞oV0三者互相确定,但都是难解 的(目前都没有多项式时间算法) 《集合论与图论》第26讲 15
《集合论与图论》第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三者互相确定, 但都是难解 的(目前都没有多项式时间算法)