← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3720

独立集内没有相邻顶点

理解等级:初级

图的独立集是顶点子集,使每条边至多有一个端点落在其中,等价于所选顶点两两不相邻。

最大独立集求最大规模;判定版本给定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