问题基本上是要证明，对于任何未加权图G（V，E），如果我们能找到一条像floor（| V |/2）那么大的简单路径，我们就能计算出哈密顿路径。
基本上哈密顿路径是多项式时间可约的长路径问题。
我试图找到一个图，在这个图中，一条大小为| v |/2的路径将映射到另一个图的哈密顿路径然而，我没有得到任何地方与这种做法。
也许有一种方法可以证明任何图都有一个比长度V/2更大的有限条路径，这意味着我们可以多次重复我们的长路径算法来找到我们的哈密顿路径但我不确定。
最佳答案
作为提示，假设您想在一个有n个节点的图中找到一个哈密顿路径如果您创建一个新的图，它是原始图的两个独立副本，并询问该新图是否具有通过n个节点的哈密顿路径，会发生什么情况？
希望这有帮助！
关于algorithm - NP完全理论:漫长的道路，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29371545/