知识卡片

普通读书笔记卡 · 3718.a

哈密顿环归约到旅行商

理解等级:高级

把无向图补成完全图:原有边费用设0,补加边费用设1,再问是否存在费用不超过0的旅行商环。

原图有哈密顿环当且仅当新图有零费用环;补边不能出现在合格环中。

这张卡片看不懂?

已有反馈 · 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