知识卡片

普通读书笔记卡 · 3717.b

覆盖与哈密顿环的双向性

理解等级:高级

若原图有k点覆盖,可让每个被选顶点对应一条穿过其关联边构件的路径,再用选择顶点连成环;每条边至少被覆盖一次,构件顶点便全被访问。

反过来,环的每条选择路径对应一个原顶点,所有构件被访问保证每条原边有被选端点。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      Now we show that the transformation from graph G to G′ is a reduction. That is, we must show that G has a vertex cover of size k if and only if G′ has a hamiltonian cycle. Suppose that G = (V, E) has a vertex cover V* ⊆ V, where |V*| = k. Let V* = {u1, u2,

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[100000,105000))。 - 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。 - 原始内容:Now we show that the transformation from graph G to G ′ is a reduction. That is, we must show that G has a vertex cover of size k if and only if G ′ has a hamiltonian cycle. Suppose that G = ( V , E ) has a vertex cover V * ⊆ V , where | V *| = k . Let V * = { u 1 , u 2 , … , u k }. As Figure 34.17 shows, we can construct a hamiltonian cycle in G