查找无向图中不包含子循环的所有循环

Question

我正在尝试找到一种快速方法，在无向图中找到所有不包含任何子循环的循环。

以下是包含此类五个周期的图表示例：

这里的周期如下：{1,2,3,4}，{1,4,5}，{5,4,7,6}，{4,3,7}，{7,3,9 ，8}

我怎么能解决这个问题？

Answer 1

不包含子循环的循环被称为“induced cycles”，如果你搜索这个术语，你可能会找到一些你会发现使用的东西。

例如，我发现这篇文章正是关于你所描述的问题：Finding and listing induced paths and cycles。

为了我个人的需要，我最近编写了一个算法，在有向图中找到没有子循环的循环，但它需要一些修改才能用于无向图，我也不确定如果在无向图上使用它会有多快。