第25讲支配,覆盖独立,匹配 支配集,独立集,点覆盖,团 边覆盖,边独立集(匹配) 最大匹配, Berge定理 完备匹配,H訕条件,t条件 秦完美匹配,Tut定理 《集合论与图论》第26讲
《集合论与图论》第26讲 1 第25讲 支配,覆盖,独立,匹配 支配集,独立集,点覆盖,团 边覆盖, 边独立集(匹配) 最大匹配, Berge定理 完备匹配, Hall条件, t条件 完美匹配, Tutte定理
支配集( dominating set) 无向图G=<V,E>,V"V 支配集:u(ueV√)vveV(u,V)∈E) 或u∈V,V∈V*,UEv 癱极小支配集:∨是支配集,其真子集都不 最小支配集:||最小的支配集 支配数:6(G)=N/,￥y*是最小支配集 《集合论与图论》第26讲
《集合论与图论》第26讲 2 支配集(dominating set) 无向图G=<V,E>, 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,E>,V"V 秦独立集:uVeV,()E 癱极大独立集:∨是独立集,其真母集都不 疋 鲁最大独立集:||最大的独立集 独立数:(G)=N,y*是最大独立集 《集合论与图论》第26讲
《集合论与图论》第26讲 5 独立集(independent set) 无向图G=<V,E>, V*⊆V 独立集: ∀u,v∈V*, (u,v)∉E 极大独立集: V*是独立集, 其真母集都不 是 最大独立集: |V*|最大的独立集 独立数: β0(G)=|V*|, V*是最大独立集