定理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*=∅. #