原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
algorithm that has vertex cover V − V′ = {w, z}, in blue. 34.5.2 The vertex-cover problem
A vertex cover of an undirected graph G = (V, E) is a subset V′ ⊆ V such that if (u, v) ∈ E, then u ∈ V′ or v ∈ V′ (or both). That is, each vertex “covers” its incident edges, and a vertex cover for G is a set of vertices that covers all the edges in E. The size of a vertex cover is the number of vertices in it. For example, the graph in Figure 34.15(b) has a vertex cover {w, z} of size 2. The vertex-cover problem is to find a vertex cover of minimum size in a given graph. For this optimization problem, the corresponding decision problem asks whether a graph has a vertex cover of a given size k. As a language, we define VERTEX-COVER = {〈G, k〉 : graph G has a vertex cover of size k}. The following theorem shows that this problem is NP-complete. Theorem 34.12 The vertex-cover problem is
NP-complete. Proof We first show that VERTEX-COVER ∈ NP. Given a graph G = (V, E) and an
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea