在三次平面图中查找哈密顿循环
我有相对较小的（40-80 个节点）立方（3-正则）平面图，我必须确定它们的哈密顿度。我知道这个任务是 NP 完全的，但我希望渐近指数时间算法对于我感兴趣的图大小来说仍然非常快。
I have relatively small (40-80 nodes) cubic (3-regular) planar graphs, and I have to decide their Hamiltonicity. I am aware of the fact that this task is NP-complete, but I hope for asymptotically exponential time algorithms that are nevertheless very fast for the graph size I am interested in.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
40 个节点似乎是可行的。您将选择 60 条边中的 40 条来包含。
让我们尝试深度优先搜索。
首先，选择一个顶点 V。您需要精确排除其 3 个关联边之一。一次尝试这 3 种可能性。当您选择要排除的边时，您将强制包含 4 条边。之后，我们将排除的边的顶点称为“已使用”。
如果您可以重复此过程 10 次，您将选择所有 40 条边，仅搜索 3^10 (59049) 种可能性。当然，在确定了足够的边之后，您将用完“孤立的”顶点。
但是，我们现在有了一个算法的想法。在每一步中，尝试选择“使用”邻居最少的顶点。实际上，选择具有 2 个使用的邻居的顶点是最好的，因为使用的边是强制的。我不确定选择具有 1 个或 0 个已用邻居的顶点是否是下一个最佳选择。两种方法都尝试一下！ （3 个使用的邻居表示搜索失败）
当我们完成拾取边时，检查它们是否形成单个循环。
你有一些示例图吗？我可能会尝试一个简单的实现。
40 nodes seems doable. You're choosing 40 of 60 edges to include.
Let's try a depth-first search.
To start, pick a vertex V. You will need to exclude exactly one of its 3 incident edges. Try these 3 possibilities one at a time. When you choose an edge to exclude, you are forcing the inclusion of 4 edges. After this, we'll call the vertices of the excluded edge "used".
If you could repeat this process 10 times, you would have chosen all 40 edges, searching only 3^10 (59049) possibilities. Of course, you'll run out of "isolated" vertices after enough edges have been determined.
But, we now have an idea for an algorithm. At each step, try picking a vertex with the fewest "used" neighbors. Actually, picking a vertex with 2 used neighbors is best, since the used edge is forced. I'm not sure if picking a vertex with 1 or 0 used neighbors is the next best. Try both ways! (And 3 used neighbors indicates a failed search)
When we're done picking edges, check if they form a single cycle.
Do you have a few sample graphs? I might try a simple implementation.
来自 http://mathworld.wolfram.com/HamiltonianCycle.html ：
“Rubin (1974) 描述了一种有效的搜索过程，可以使用推论在图中找到部分或全部汉密尔顿路径和电路，从而大大减少回溯和猜测。”
该论文在这里出售：http://portal.acm.org/itation.cfm ?id=321850.321854
from http://mathworld.wolfram.com/HamiltonianCycle.html :
"Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork."
The paper is for sale here: http://portal.acm.org/citation.cfm?id=321850.321854