Dán*_*rga 6 hamiltonian-cycle planar-graph
我有相对较小的(40-80个节点)立方(3-regular)平面图,我必须决定它们的汉密尔顿性.我知道这个任务是NP完全的,但我希望渐近指数时间算法对我感兴趣的图形大小来说非常快.
40 个节点似乎是可行的。您将选择 60 条边中的 40 条来包含。
让我们尝试深度优先搜索。
首先，选择一个顶点 V。您需要精确排除其 3 个关联边之一。一次尝试这 3 种可能性。当您选择要排除的边时，您将强制包含 4 条边。之后，我们将排除的边的顶点称为“已使用”。
如果您可以重复此过程 10 次，您将选择所有 40 条边，仅搜索 3^10 (59049) 种可能性。当然，在确定了足够的边之后，您将用完“孤立的”顶点。
但是，我们现在有了一个算法的想法。在每一步中，尝试选择“使用”邻居最少的顶点。实际上，选择具有 2 个使用的邻居的顶点是最好的，因为使用的边是强制的。我不确定选择具有 1 个或 0 个已用邻居的顶点是否是下一个最佳选择。两种方法都尝试一下！（使用 3 个邻居表示搜索失败）
当我们完成拾取边缘后，检查它们是否形成一个循环。
你有一些示例图吗？我可能会尝试一个简单的实现。