作者suck5566bird (5566最爱suck183)
看板Prob_Solve
标题[问题] 汉米耳顿问题
时间Sun Jan 13 21:30:56 2008
想请问一下
如果要用Computation theory里的证明来证
有汉米尔顿路径若已知道是NP-HARD
怎麽说明全都是正的Weight的有向图里找最长路径也是NP-HARD?
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.28.113
1F：推 march20:把 Hamilton Cycle map 到你说的这个问题即可 01/14 05:45
2F：推 march20:hint: 最长路径什麽时候会是 hamilton path 01/14 05:47
3F：推 march20:口也, 第一个推文把 cycle 改成 path XD 01/14 05:47