hamiltonian-cycle - 在三次平面图中寻找哈密顿圈

Question

我有相对较小(40-80 个节点)三次(3-正则)平面图，我必须确定它们的哈密顿性。我知道这个任务是 NP 完全的，但我希望渐近指数时间算法对于我感兴趣的图大小来说仍然非常快。

Answer 1

40 个节点似乎是可行的。您正在选择要包含的 60 条边中的 40 条。

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

首先，选择一个顶点 V。您需要准确地排除它的 3 个入射边之一。一次尝试这 3 种可能性。当您选择要排除的边时，您将强制包含 4 个边。在此之后，我们将排除边的顶点称为“已使用”。

如果您可以重复此过程 10 次，您将选择所有 40 条边，仅搜索 3^10 (59049) 种可能性。当然，在确定了足够多的边后，“孤立”顶点将用完。

但是，我们现在有了一个算法的想法。在每一步，尝试选择一个“使用”邻居最少的顶点。实际上，选择具有 2 个使用过的邻居的顶点是最好的，因为使用的边是强制的。我不确定选择具有 1 个或 0 个已用邻居的顶点是否是次优。两种方法都试试! (3 个使用过的邻居表示搜索失败)

当我们完成拾取边缘后，检查它们是否形成一个循环。

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