知识卡片
顶点覆盖要覆盖每条边
无向图的顶点覆盖是顶点子集,使每条边至少有一个端点被选中。
最小顶点覆盖是优化问题;给定k问是否存在大小为k的覆盖是判定问题,给出的顶点集合可逐边验算。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
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