原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
checks that the sum is at most k. This process can certainly be done in polynomial time.
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
all vertices v ∈ V.) The instance of TSP is then 〈G′, c, 0〉, which can be created in poly
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea