点覆盖集与独立集续 推论F是极小点覆盖集当且仅当V(G)-F是极大点独 立集 证明： 1.F是点覆盖集当且仅当V(G)-F是点独立集 2.「是极小点覆盖集台F中去除任意一些点就会将至 少一条边的两个端点都去除台V(G)-F中加入任意 一些点就会将至少一条边的两个端点都加入台 V(G)-F是极大点独立集 16点覆盖集与独立集 (续) •推论 F是极小点覆盖集当且仅当V(G)-F是极大点独 立集。 证明： 1. F是点覆盖集当且仅当V(G)-F是点独立集 2. F是极小点覆盖集 ⇔ F中去除任意一些点就会将至 少一条边的两个端点都去除 ⇔ V(G)-F中加入任意 一些点就会将至少一条边的两个端点都加入 ⇔ V(G)-F是极大点独立集 16