← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.782Z

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