在立体平面图中寻找哈密顿回路

Question

6

我有一些相对较小的（40-80个节点）立方体（3-正则）平面图，需要判断它们是否为哈密顿图。我知道这个任务是NP完全问题，但我希望能找到渐进指数时间算法，尽管对于我感兴趣的图形大小来说非常快速。

- Dániel Varga

2个回答

2

来自http://mathworld.wolfram.com/HamiltonianCycle.html： “Rubin (1974) 描述了一种有效的搜索算法，可以通过推导大大减少回溯和猜测来在图中找到一些或所有哈密顿路径和回路。”

- Tom Sirgedas

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tom Sirgedas · Accepted Answer

40个节点似乎可行。您需要选择其中的40个边中的60个来包括。

让我们尝试深度优先搜索。

首先，选择一个顶点V。您需要排除它的3条关联边中的一条。逐个尝试这3种可能性。当您选择要排除的边时，您将强制包括4条边。此后，我们将称被排除的边的顶点为“已用”。

如果您可以重复此过程10次，您将仅搜索3^10（59049）种可能性即可选择所有40条边。当然，随着足够多的边被确定，您将耗尽“孤立”的顶点。

但是，我们现在有了一个算法的想法。在每个步骤中，尝试选择具有最少“已用”邻居的顶点。实际上，选择具有2个已用邻居的顶点最好，因为使用的边是强制的。我不确定选择具有1个或0个已用邻居的顶点是否是下一个最佳选择。尝试两种方式！（而3个已用邻居表示搜索失败）

当我们完成选择边时，请检查它们是否形成单个循环。

您有几个示例图吗？我可能会尝试一个简单的实现。