知识卡片
独立集内没有相邻顶点
图的独立集是顶点子集,使每条边至多有一个端点落在其中,等价于所选顶点两两不相邻。
最大独立集求最大规模;判定版本给定k问能否找到至少k个。与团问题相比,邻接条件正好相反。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
An independent set of a graph G = (V, E) is a subset V′ ⊆ V of vertices such that each edge in E is incident on at most one vertex in V′. The independent-set problem is to find a maximum-size independent set in G. a. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[120000,125000))。
- 结论依据:原文归约策略、习题定义与脚注限定;图34.20–34.21已核对,习题未给出的证明不作既成结论。
- 原始内容:An independent set of a graph G = ( V , E ) is a subset V ′ ⊆ V of vertices such that each edge in E is incident on at most one vertex in V ′. The independent-set problem is to find a maximum-size independent set in G . a. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. ( Hint: Reduce from the clique