问题标签 [hamiltonian-cycle]

我怎样才能证明一个无向图甚至没有。节点数（至少有一个行或列是偶数 - 当然不包括折线图）有一个哈密顿循环？

我已经设法证明它是一个二分图，并且（结果）所有循环的长度都是偶数。

但是，我究竟如何证明至少存在一个这样的循环来覆盖所有可用节点呢？

问题是使用哈密顿循环 Hcycle(V,E) 函数来测试图 G 是否包含哈密顿路径，该函数在 G 是否包含哈密顿循环时给出输出真或假。

我必须编写一个具有多项式时间复杂度的程序，它必须使用一个必须为这个问题提供输出的哈密顿循环函数来确定无向图 G 是否包含至少一个哈密顿路径。

我还需要编写一个具有相反问题的程序。（使用 Hpath 函数判断图形是否包含 Hemiltonian 循环）。

我找不到这个问题的解决方案。我只能同时使用 Hcycle 和 Hpath 一次。

我们假设函数 Hcycle 和 Hpath 以线性时间复杂度运行。

我一直在寻找一些哈密顿循环算法，但我找不到任何实现，甚至没有一个伪代码！我什至不需要输出循环，只需检查图形是否有循环。输入是一个具有 V 个顶点和 E 个边的图。另外，我想有一个算法来检查一个图是否有哈密顿路径。我不需要输出路径，只需检查它是否有一个。两者都应该在多项式时间内。

我有一个很大的加权图。我想计算一条近似最短的哈密顿路径，它以最低的成本通过所有节点。我的图表非常大，不适合我的记忆。所以我决定随机忽略一些边缘并将其余的加载到内存中。但问题是大多数 java TSP 实现都需要一个完整的图表，在我的情况下需要大量内存，而我没有那么多内存。有没有在 imcpmlete 图上计算 TSP 的 java 库？我的staretegy是我将初始顶点集分成更小的部分。我为每个计算了最短的哈密顿路径，然后我连接了所有最短的哈密顿路径。它是 TSP 的一个很好的近似值吗？有谁知道大图的 TSP 更好的近似算法？

我被告知要确定一个图是否有哈密顿路径，它不会在多项式时间内计算。假设我们可以在多项式时间内解决它，我该如何证明呢？这是不可能的，因为它是NP难题？

所以我想出了这个实现来解决 8*8 棋盘的骑士之旅。但似乎它需要很长时间才能运行（以至于我不得不停止它）。但是，如果我用注释中写的数组替换 dx、dy 数组，程序就会像魔术一样工作并给出输出。他们说它巧妙地选择了数组，因此暴力算法很幸运能够快速找到解决方案。

但是首先是如何提出这个数组的，这个数组（dx，dy）是我从其他代码中得到的。所以谁能解释我为什么这段代码适用于这些数组（在评论中）而不是我的。

给定 n 作为节点数和边作为边列表

谁能告诉我我的代码有什么问题。它适用于某些实例，但不适用于所有实例

考虑一个 n 阶图，其中 n 是 1 mod 4（即五边形、九边形等），并假设它是 (n-1)/2-正则图。此外（可能可选）假设它和它的补码都是连接的。

这种类型的图是否可以被验证为哈密顿量，如果可以，证明将如何进行？

我正在寻找一种比指数更快的算法，它将在旅行推销员问题中找到任何循环。不管循环有多糟糕，它只需要一个循环。那么，我真正在寻找的是一种用于哈密顿电路的算法。从一个点开始，到达所有其他点，然后在这样的图表上的起点结束的东西：http: //neogen.amdusers.com/wikipics/projects/tsp.png

到目前为止，我发现这个随机算法似乎不适用于我的示例案例： http: //www.princeton.edu/~achaney/tmve/wiki100k/docs/Hamiltonian_path_problem.html

还有我无法理解的“帕尔默算法”： 哈密顿循环的帕尔默算法

是否有超过这两种算法可以做到这一点？

我已经读过，查找图中是否存在哈密顿路径的问题是 NP 完全的，并且由于Dijkstra 的最短路径算法在多项式时间内运行，因此无法对其进行修改以找到最短的哈密顿路径。（这个逻辑有效吗？）

但是，如果给定无向图上的两个节点（比如 A 和 Z）（所有边的成本都非负），并且给定节点（A 和 Z）至少存在一条哈密顿路径，该怎么办？作为终点。鉴于这些规范，现在是否可以修改 Dijkstra 的算法以找到以 A 和 Z 作为端点的最短哈密顿路径？（多项式时间）

注意：我只关心从两个节点中找到最短的哈密顿路径。例如，如果有一个包含 26 个节点（标记为 A 到 Z）的图，那么通过所有点但从 A 开始并在 Z 结束的最短路径是什么。（我不关心找到其他不同的哈密顿路径端点，只有 A 和 Z）

附加问题：如果答案是“否”，但有另一种算法可以用来解决这个问题，它是什么算法，它的时间复杂度是多少？

（注意：这个问题将“hamiltonian-cycle”作为标签，即使我正在寻找 Hamiltonian PATH，因为我没有足够的代表来制作标签“hamiltonian-path”。但是，假设 A 和 Z恰好由一条边连接，那么最短的哈密顿路径可以通过找到最短的哈密顿循环，然后去除连接 A 和 Z 的边）