algorithm - 是否有任何有效的算法可以找到无向图中最长循环的长度？

Question

我想知道是否有任何有效的算法可以找到图中最长循环的长度？

该图是一个无向图。

该算法不必告诉循环中的顶点是什么，只需知道长度。

标签： algorithmgraph-algorithmcycle

Answer 1

在图中找到最长循环的问题是NP-hard，因为解决这个问题可以回答“这个图是 hamiltonian 吗？ ”（它是否具有 hamiltonian 循环）这个问题，这本身就是一个 NP 完全问题。
所以，事实上，没有有效的算法可以做到这一点。
有一些基于矩阵乘法的方法可以在k图中找到长度的循环。您可以在此问题中找到有关使用矩阵乘法查找循环的解释。但请注意，矩阵乘法方法允许检测walks2 个顶点之间的给定长度，并且在步行中允许顶点的重复。