独立集与顶点覆盖相互规约问题 _覆盖

智者不为愚者谋，勇者不为怯者死。这篇文章主要讲述独立集与顶点覆盖相互规约问题相关的知识，希望能为你提供帮助。

目录

1.1 Theorem. INDEPENDENT-SET ≡ P VERTEX-COVER.
- 1.1.1 证明充分性
- 1.1.2 证明必要性

1.1 Theorem. INDEPENDENT-SET ≡ P VERTEX-COVER.Pf. We show S is an independent set of size k iff V ? S is a vertex cover
of size n – k.
如果图S有一个顶点个数为K的独立集存在的条件是：当且仅当V-S顶点覆盖的大小为n-k;
1.1.1 证明充分性
?

Let S be any independent set of size k.
V ? S is of size n – k.
Consider an arbitrary edge (u, v) ∈ E.
S independent ? either u ? S, or v ? S, or both.
? either u ∈ V ? S, or v ∈ V ? S, or both.
Thus, V ? S covers (u, v).

1.1.2 证明必要性
【独立集与顶点覆盖相互规约问题】?

Let V ? S be any vertex cover of size n – k.
S is of size k.
Consider an arbitrary edge (u, v) ∈ E.
V ? S is a vertex cover ? either u ∈ V ? S, or v ∈ V ? S, or both.
? either u ? S, or v ? S, or both.
Thus, S is an independent set.