知识卡片
哈密顿环归约到旅行商
把无向图补成完全图:原有边费用设0,补加边费用设1,再问是否存在费用不超过0的旅行商环。
原图有哈密顿环当且仅当新图有零费用环;补边不能出现在合格环中。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
To prove that TSP is NP-hard, we show that HAM-CYCLE ≤P TSP. Given an instance G = (V, E) of HAM-CYCLE, construct an instance of TSP by forming the complete graph G′ = (V, E′), where E′ = {(i, j) : i, j ∈ V and i ≠ j }, with the cost function c defined as (Because G is undirected, it contains no self-loops, and so c(v, v) = 1 for
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[105000,110000))。
- 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。
- 原始内容:To prove that TSP is NP-hard, we show that HAM-CYCLE ≤ P TSP. Given an instance G = ( V , E ) of HAM-CYCLE, construct an instance of TSP by forming the complete graph G ′ = ( V , E ′), where E ′ = {( i , j ) : i, j ∈ V and i ≠ j }, with the cost function c defined as (Because G is undirected, it contains no self-loops, and so c ( v, v ) = 1 for