← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3716

顶点覆盖要覆盖每条边

理解等级:初级

无向图的顶点覆盖是顶点子集,使每条边至少有一个端点被选中。

最小顶点覆盖是优化问题;给定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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[90000,95000))。 - 结论依据:原文§34.4–34.5的3-CNF、团、顶点覆盖和哈密顿环归约;图已核对,跨单元证明留待续读。 - 原始内容: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