NP完全理论：长路径
NP complete Theory: Long Path
这个问题基本上是为了证明对于任何未加权的图 G(V,E)，如果我们能找到一条与 floor(|V|/2) 一样大的简单路径，我们就可以计算哈密顿路径。
基本上哈密顿路径是多项式时间可简化为长路径问题。
我试图找到一个图，其中大小为 |v|/2 的路径将映射到另一个图的哈密顿路径。然而，我对这种方法一无所获。
也许有一种方法可以证明对于任何图存在有限数量的大于长度 |V|/2 的路径，这意味着我们可以多次重复我们的长路径算法来找到我们的哈密顿路径。但我不确定这一点。
作为提示，假设您想在具有 n 个节点的图中找到哈密顿路径。如果您创建一个新图，它是原始图的两个独立副本，并询问该新图是否具有穿过 n 个节点的哈密顿路径，会发生什么？
希望对您有所帮助！
这个问题基本上是为了证明对于任何未加权的图 G(V,E)，如果我们能找到一条与 floor(|V|/2) 一样大的简单路径，我们就可以计算哈密顿路径。
基本上哈密顿路径是多项式时间可简化为长路径问题。
我试图找到一个图，其中大小为 |v|/2 的路径将映射到另一个图的哈密顿路径。然而，我对这种方法一无所获。
也许有一种方法可以证明对于任何图存在有限数量的大于长度 |V|/2 的路径，这意味着我们可以多次重复我们的长路径算法来找到我们的哈密顿路径。但我不确定这一点。
作为提示，假设您想在具有 n 个节点的图中找到哈密顿路径。如果您创建一个新图，它是原始图的两个独立副本，并询问该新图是否具有穿过 n 个节点的哈密顿路径，会发生什么？
希望对您有所帮助！