1. 首页
  2. 问答
  3. 查找立方平面图中的哈密尔顿周期

查找立方平面图中的哈密尔顿周期

2010-07-05 87 views
6

我有相当小的（40-80节点）立方（3-规则）平面图，我必须决定他们的哈密尔顿性。我知道的事实，这任务是NP完全，但我希望渐近指数时间的算法是仍然是在图形大小我很感兴趣，非常快查找立方平面图中的哈密尔顿周期

来源

2010-07-05 Dániel Varga

回答

3

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

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

要开始，选择一个顶点V.您将需要排除其3个入射边缘中的一个。一次尝试这三种可能性。当您选择要排除的边时，您将强制包含4条边。在此之后，我们将调用被排除的边的顶点“used”。

如果你可以重复这个过程10次，你会选择所有40条边，只搜索3^10（59049）个可能性。当然，在足够的边界被确定之后，你会用完“孤立”的顶点。

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

当我们完成拾取边缘时，检查它们是否形成单个周期。

你有几个样本图吗？我可能会尝试一个简单的实现。

来源

2010-07-06 22:51:00

相关问题

 相关问题