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

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

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

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

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

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

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

看下是否有所帮助：

哈密顿回路算法详解 - Dragonir - 博客园 【转】哈密顿回路 原文链接:http://www.cnblogs.com/Ash-ly/p/5452580.html 概念: 哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿 https://www.cnblogs.com/dragonir/p/6011561.html

可以参考这个

哈密顿回路算法分析_星入云野的博客-CSDN博客_hamilton回路算法 提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言一、哈密顿回路问题分析二、问题的解决方案三、算法问题求解中所遇到的问题及解决方案四、算法测试总结前言提示：这里可以添加本文要记录的大概内容：例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。提示：以下是本篇文章正文内容，下面案例可供参考一、哈密顿回路问题分析问题描述：哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过 https://blog.csdn.net/zjx990708/article/details/118440105

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

哈密顿圈问题是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

由于多项式问题具有传递性,因此只需证明一个已知的NP完全问题能够在多项式时间内归约到该问题即可。
https://zhuanlan.zhihu.com/p/146951959

在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的 可以在多项式时间类判断一个回路是否是哈密顿回路 但目前没有算法直接解出哈密顿回路