知识卡片
覆盖与哈密顿环的双向性
若原图有k点覆盖,可让每个被选顶点对应一条穿过其关联边构件的路径,再用选择顶点连成环;每条边至少被覆盖一次,构件顶点便全被访问。
反过来,环的每条选择路径对应一个原顶点,所有构件被访问保证每条原边有被选端点。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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