点覆盖集与点独立集的关系 定理2.设G=<V,E>中无孤立点,V(VcV为G的点覆盖,当且仅 当VV*为G的点独立集 证明 (必要性) 假设存在 Vi, ViEV-Vi,且vy∈E.由于顶点v和v都不在V 中,这显然与“V是点覆盖”相矛盾.所以,V-V为点独立集 (充分性 由于V-V是点独立集,因此,任意一条边的两个端点至少有 个在V中.根据定义可知,V是G的点覆盖 推论设G是n阶无孤立点的图,则V是G的极小最小)点覆盖,当且仅当 VV是G的极大(最大)点独立集,从而有α+βB0=n7 点覆盖集与点独立集的关系 定理2. 设G = <V, E>中无孤立点, V*(V*⊂V)为G的点覆盖, 当且仅 当V-V*为G的点独立集。 证明: (必要性) 假设存在vi, vj∈V - V*, 且(vi, vj) ∈ E. 由于顶点vi和vj都不在V* 中, 这显然与“V*是点覆盖”相矛盾. 所以, V - V*为点独立集。 (充分性) 由于V - V*是点独立集, 因此, 任意一条边的两个端点至少有一 个在V*中. 根据定义可知, V*是G的点覆盖。 推论 设G是n阶无孤立点的图, 则V*是G的极小(最小)点覆盖, 当且仅当 V-V*是G的极大(最大)点独立集, 从而有α0 + β0 = n