algorithm - 如何使用 BFS 在图中找到哈密顿循环？（条件是图正好是哈密顿）

Question

我正在尝试解决哈密顿循环问题。

我的任务条件是：

该组由 N 人组成。在其中，每个人都有 N / 2 个朋友。友谊是对称的（如果 A 是朋友 B，那么 B 是朋友 A）。小组中的一个人有一本书（他的号码 X），每个人都想阅读，然后与其他一些人讨论。

需要确定转让书的方法，即它会访问每个人一次，只在朋友之间传递，最后归还给它的主人。

也就是说，它满足狄拉克定理的条件。

在小图上，我的解决方案可以正常工作，但在大图上，我的解决方案给出了时间限制例外。

有什么方法可以比 O(n!) 更快地解决它？

标签： algorithmmathgraphgraph-algorithmhamiltonian-cycle

Answer 1

有一种多项式时间算法可以在每个顶点度数至少为 N/2 的图中找到哈密顿循环。

它在“关于哈密顿性的狄拉克定理的简单扩展” Yasemin Büyükçolak、Didem Gözüpek、Sibel Özkan、Mordechai Shalom中进行了描述。