点独立集与支配集的关系 定理1.设G=<V,E>中无孤立点,则G的极大点独立集都是G的极 小支配集。 证明 设V是G中的任意一个极大独立集.VVeV-V,一定丑v∈ V,使得(v,v)∈E.否则彐u∈VV不与V中任何顶点相邻,则 U{u}就是一个更大的独立集,这与V是极大独立集相矛盾.所 以,V是G的支配集。 由“V是点独立集”可知,V1*cV,V-V*中的顶点都不受 V1*中的顶点支配,即V*不是支配集.所以,V是极小支配集 55 点独立集与支配集的关系 定理1. 设G = <V, E>中无孤立点, 则G的极大点独立集都是G的极 小支配集。 设 V*是G中的任意一个极大独立集. ∀v∈V - V*, 一定 ∃v’ ∈ V*, 使得 (v, v’) ∈ E. 否则∃u∈V-V*不与V*中任何顶点相邻, 则 V*∪{ u }就是一个更大的独立集, 这与V*是极大独立集相矛盾. 所 以, V*是G的支配集。 由“V*是点独立集”可知, ∀V1* ⊂ V*, V* - V1*中的顶点都不受 V1*中的顶点支配, 即V1*不是支配集. 所以, V*是极小支配集。 证明: