问题标签 [hamiltonian-cycle]

先来几个定义：

定义 1

如果对于每对不相邻的顶点 u 和 v，d(u) + d(v)>=n，其中 n = |V|，则图 G = (V, E) 称为“密集”。d(*) 表示顶点的度数 *

定义 2

G 上的“哈密顿循环”是一个顶点序列 (vi1, vi2,....vin, vi1) 使得 vil != vih 对所有 l!=h 和 {vil, vil} 是 G 的一条边.

问题是：编写一个程序，给定一个稠密的无向图 G = (V; E) 作为输入，确定 G 是否承认 G 上的哈密顿循环并输出该循环，如果有的话，或者输出“N”如果没有。

我的解决方案是查找从源开始的所有可能路径，并检查是否存在返回该源的路径。不幸的是，这个解决方案效率不高。

有什么建议么？谢谢你。

在“密集”图中，我正在尝试使用Palmer's Algorithm构建哈密顿循环。但是，我需要对这个算法进行更多解释，因为当我实现它时它对我不起作用。维基百科的解释似乎有一个不清楚的部分。

如果有人更清楚地解释它或给我一些阅读链接，我将不胜感激。

这是算法语句：

Palmer (1997) 描述了以下简单算法，用于在满足 Ore 条件的图中构造哈密顿循环。将顶点任意排列成一个循环，忽略图中的邻接关系。当循环包含两个连续的顶点vi并且vi + 1在图中不相邻时，执行以下两个步骤：

• 搜索一个索引j，使得四个顶点vi、vi + 1、vj和vj + 1都是不同的，并且图包含从vitovj + 1和 from vjto的边vi + 1

• vi + 1反转和vj（包括）之间的循环部分。

更具体地说，我没有得到他们说的部分：在这种情况下，“将顶点任意排列成一个循环”，这是正确的做法：0,1,2,3,4,0

它们是什么意思：“扭转循环的一部分”？

给定一个具有 n² 路径节点的图，并且假设起始节点始终位于右上角（A 点），而结束节点始终位于右下角（B 点），我需要编写一个 C# 程序确定给定 n 的从 A 到 B 的哈密顿路径数（假设 n <=10）。换句话说，我需要找到从 A 开始到 B 结束的每条路径，其中每个节点只被访问一次，并且节点之间的移动被限制为左、右、上、下（无对角线）。

例如，如果 n = 5，则一种可能的路径将是此图像中显示的路径：

理想情况下，我想开发一种利用一些启发式的智能算法，但现在我只需要开发一种蛮力方法就可以开始了。我假设我使用广度优先搜索，但我真的不知道从哪里开始使用 C# 实现它。

有没有一种算法可以在 v^2 时间内找到尽可能长的哈密顿循环。我正在运行一个程序，该程序需要在稀疏图（最大 4v 边）上找到循环，根据我的计算，我需要 v^2 或更好。我知道要在 v^2 中操作，它必须是启发式的，并且可能不是很准确。请告诉我这是否不可能，因为我不知道这是否可能。

我正在尝试做 c++ 程序。我正在尝试解决我有很多点的问题。现在我需要找到通过所有点的路径。这实际上不是 TSP，因为根据我对 TSP 的了解，可以从所有点移动到其他所有点。但在我的情况下，点之间的路径网络是固定的，我只需要找到穿过所有点的合适路径，前提是所有点可能与其他点没有连接......所以我应该遵循什么算法。

我想生成一个完整的无向图的所有哈密顿循环（循环和反转算作重复的集合的排列，并且被排除在外）。

例如，{1,2,3} 的排列是

标准排列：

我希望程序/算法为我打印的内容：

由于 321 只是向后 123，所以 312 只是 123 旋转了一个位置，依此类推。

我看到很多关于给定集合具有的这些循环数量的讨论，以及查找图是否具有哈密顿循环的算法，但没有关于如何在完整的无向图中枚举它们（即一组数字可以在集合中的任何其他数字之前或之后）。

我真的很想要一个算法或 C++ 代码来完成这个任务，或者如果你能指导我到哪里有关于这个主题的材料。谢谢！

我有一个具有 N 个节点和 2N-3 条边的连接的无向图。您可以将图视为构建在现有初始图的基础上，该图具有 3 个节点和 3 条边。添加到图中的每个节点都与图中的现有节点有 2 个连接。当所有节点都添加到图中（总共添加 N-3 个节点）时，构建最终图。

最初我被问到，这个图中可以访问一次的最大节点数是多少（初始节点除外），即给定图的最大哈密顿路径中包含的最大节点数是多少？（好吧，说最大哈密顿路径不是一个有效的短语，但考虑到问题的性质，我需要找到一次访问的最大节点数，并且行程在初始节点处结束。我认为它可以被视为子图是哈密顿量，由最大数量的节点组成，因此是最大可能的哈密顿路径）。

由于没有要求我找到路径，因此我应该首先检查给定数量的节点是否存在哈密顿路径。我知道平面图和循环图s (C _n ) 是哈密顿图（我也知道哈密顿图的 Ore 定理，但我将要处理的图不会是一个很有可能的密集图，因此使 Ore 的定理很漂亮在我的情况下没用）。因此，我需要找到一种算法来检查该图是否为循环图，即是否存在一个包含给定图的所有节点的循环。

由于 DFS 用于检测周期，我认为对 DFS 进行一些小的操作可以帮助我检测我正在寻找的内容，例如跟踪探索的节点，最后检查最后访问的节点是否与初始节点有连接。不幸的是，我无法通过这种方法取得成功。

我尝试的另一种方法是排除一个节点，然后尝试从另一个相邻节点开始到达其相邻节点。根据所选的相邻节点，该算法可能无法给出正确的结果。

我几乎被困在这里。你能帮我想出另一种算法来告诉我该图是否是循环图吗？

编辑

我在评论的帮助下意识到（谢谢你）：

循环图由一个循环组成，有 N 个边和 N 个顶点。如果存在一个包含给定图的所有节点的循环，那就是哈密顿循环。-纳米

我实际上是在寻找一条哈密顿路径，我并不打算这样做:) 再想一想，我认为在构建图的同时检查图的哈密顿属性会更有效，这也是我正在寻找的: 时间效率。

经过一番思考，我认为无论节点数量是多少，由于节点添加标准，该图似乎是哈密顿量。问题是我无法确定，也无法证明。以这种方式添加节点，即添加具有 2 条边的新节点，将添加的节点连接到现有节点，是否会改变图的哈密顿属性？如果它不改变哈密顿性质，那又如何呢？如果它确实改变了，又是怎么回事？谢谢。

编辑#2

我再次意识到，按照我描述的方式构建图形可能会改变哈密顿量。考虑如下给出的输入：

这些输入表示第 4 个节点连接到节点 1 和节点 3，第 5 个节点连接到节点 2 和节点 3。. .

第 4 和第 7 个节点连接到相同的节点，从而将可以仅访问一次的最大节点数降低 1。如果我检测到这些冲突（不包括诸如 3 3 之类的输入，这是您建议的示例由于问题表明新添加的边连接到其他 2 个节点）并降低最大节点数，从 N 开始，我相信我可以得到正确的结果。

看，我不选择连接，它们是给我的，我必须找到最大值。节点数。

我认为在构建图形时计算相同的连接数并从 N 中减去相同的连接数会得到正确的结果吗？你能证实这一点还是这个算法有缺陷？

我正在尝试实现一种使用递归将所有可能的哈密顿循环添加到列表的方法。到目前为止，我的停止条件还不够，我在将顶点添加到列表的行中得到“OutOfMemoryError: Java heap space”：

有人可以建议我做错了什么还是我的方法完全不正确？

编辑：正如评论中所建议的，罪魁祸首是父数组，导致无限循环。我无法更正它，我更改了数组以存储子元素。现在一切似乎都奏效了：

我指的是Skienna的算法书。

测试图是否G包含 a的问题Hamiltonian path是NP-hard，其中哈密顿路径P是对每个顶点仅访问一次的路径。与哈密顿循环问题不同，G 中从 P 的结束顶点到起始顶点不必有一条边。

给定一个有向无环图 G( · DAG)，给出一个O(n + m)时间算法来测试它是否包含哈密顿路径。

我的做法，

我打算使用DFS和Topological sorting。但是我不知道如何在解决问题时将这两个概念联系起来。如何使用拓扑排序来确定解决方案。

有什么建议么？

是否有针对被认为“难以”解决哈密顿循环的孔的网格图的数据库或引用？