c++ - 检查稠密图中是否存在汉密尔顿环

Question

先来几个定义：

定义 1

如果对于每对不相邻的顶点 u 和 v，d(u) + d(v)>=n，其中 n = |V|，则图 G = (V, E) 称为“密集”。d(*) 表示顶点的度数 *

定义 2

G 上的“哈密顿循环”是一个顶点序列 (vi1, vi2,....vin, vi1) 使得 vil != vih 对所有 l!=h 和 {vil, vil} 是 G 的一条边.

问题是：编写一个程序，给定一个稠密的无向图 G = (V; E) 作为输入，确定 G 是否承认 G 上的哈密顿循环并输出该循环，如果有的话，或者输出“N”如果没有。

我的解决方案是查找从源开始的所有可能路径，并检查是否存在返回该源的路径。不幸的是，这个解决方案效率不高。

有什么建议么？谢谢你。

Answer 1

根据Ore's theorem，满足定义 1 的图总是有一个哈密顿循环，而Palmer 的算法会给你一个 O(n ² )。

Answer 2

问题是NP难的。所以我不希望任何解决方案比蛮力更快。