第25讲支配,覆盖独立,匹配 支配集,独立集,点覆盖,团 边覆盖,边独立集(匹配) 最大匹配, Berge定理 完备匹配,H訕条件,t条件 秦完美匹配,Tut定理 《集合论与图论》第26讲
《集合论与图论》第26讲 1 第25讲 支配,覆盖,独立,匹配 支配集,独立集,点覆盖,团 边覆盖, 边独立集(匹配) 最大匹配, Berge定理 完备匹配, Hall条件, t条件 完美匹配, Tutte定理
支配集( dominating set) 无向图G=,V"V 支配集:u(ueV√)vveV(u,V)∈E) 或u∈V,V∈V*,UEv 癱极小支配集:∨是支配集,其真子集都不 最小支配集:||最小的支配集 支配数:6(G)=N/,￥y*是最小支配集 《集合论与图论》第26讲
《集合论与图论》第26讲 2 支配集(dominating set) 无向图G=, V*⊆V 支配集: ∀u(u∈V-V*→∃v(v∈V*∧(u,v)∈E)) 或 ∀u∈V-V*, ∃v∈V*, uEv 极小支配集: V*是支配集, 其真子集都不 是 最小支配集: |V*|最小的支配集 支配数: γ0(G)=|V*|, V*是最小支配集
支配集(例) 星形图S:{{v1V2,…,Vn1,7S)=1 轮图W:{vV3y5…,n23,76W 《集合论与图论》第26讲
《集合论与图论》第26讲 3 支配集(例) 星形图Sn: {v0},{v1,v2,…,vn-1}, γ0(Sn)=1 轮图Wn: {v0},{v1,v3,v5…,vn-2}, γ0(Wn)=1 v0 v1 v2 v3 v5 v4
定理13.1 定理13.1:无向图G无孤立点,V是极小 支配集,则存在∨2也是极小支配集,且 V*⌒V2*= 证明:V是极小支配集,则V∨也是支配 集(反证:否则,u∈ V VVEV-V, uVgE,V1*心还是支配集矛盾 ∨∨1是支配集,则V-V1*中有子集是极小 支配集设为V2.则*⌒V2=⑦.# 《集合论与图论》第26讲
《集合论与图论》第26讲 4 定理13.1 定理13.1: 无向图G无孤立点,V1*是极小 支配集,则存在V2*也是极小支配集,且 V1*∩V2*=∅. 证明: V1*是极小支配集,则V-V1*也是支配 集.(反证: 否则, ∃u∈V1*, ∀v∈V-V1*, (u,v)∉E, V1*-{u}还是支配集,矛盾.) V-V1*是支配集,则V-V1*中有子集是极小 支配集,设为V2*. 则V1*∩V2*=∅. #
独立集( ndependent set 无向图G=,V"V 秦独立集:uVeV,()E 癱极大独立集:∨是独立集,其真母集都不 疋 鲁最大独立集:||最大的独立集 独立数:(G)=N,y*是最大独立集 《集合论与图论》第26讲
《集合论与图论》第26讲 5 独立集(independent set) 无向图G=, V*⊆V 独立集: ∀u,v∈V*, (u,v)∉E 极大独立集: V*是独立集, 其真母集都不 是 最大独立集: |V*|最大的独立集 独立数: β0(G)=|V*|, V*是最大独立集
独立集(例) 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≌V 点覆盖:eeE→ V(VEVAV关联e) 或ve∈E,丑VeV,v关联e 癱极小点覆盖:∨是点覆盖,其真子集都不 静最小点覆盖:||最小的点覆盖 点覆盖数:(G=V,V是最小点覆盖 《集合论与图论》第26讲
《集合论与图论》第26讲 9 点覆盖(vertex cover) 无向图G=, 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
