已知哈密顿回路问题对无向图是NP完全的，证明哈密顿回路问题对于有向图也是NP完全的。

Question

已知哈密顿回路问题对无向图是NP完全的，证明哈密顿回路问题对于有向图也是NP完全的。

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。

我的想法：
第一步：
已知哈密顿回路问题对无向图是NP完全的，那可以说明对应的有向图也NP的。

那么对应的有向哈密顿通路问题也是NP完全的。指定起点或终点，或同时指定起点和终点也还是NP完全的。对于无圈有向图，有向哈密顿通路能在多项式时间内得到解决。

第二步：证明无向问题可以在多项式时间归约到有向图，

疑问：具体应该如何规约，是需要构建一个界限吗和含权图G？

Answer 1

可以参考下这篇文章，希望对你有帮助：

哈密顿圈问题是NP完全的_浪在冰城的博客-CSDN博客_哈密顿回路是np问题吗 【哈密顿圈问题】对于一个有向图G=(V,E),如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。即，哈密顿圈构成一条经过所有的顶点，没有重复的“路线”。如图6是一个含有哈密顿圈的图。图6 一个含有哈密顿圈的有向图证明哈密顿圈问题是NPC的，可以通过证明3-SAT≤p\leq_p≤p​哈密顿圈来得到。【3-SAT≤p\leq_p≤p​哈密顿圈】构造方法如下:(1)对于每一个... https://blog.csdn.net/Valieli/article/details/104360907