枚举有向图中所有最小的有向环

Question

我有一个有向图，我的问题是枚举这个图的所有最小（不能被其他循环的并集构造出来的循环）有向循环。这与Tarjan算法输出的结果不同。例如，在这个维基百科页面上的有向图中，我想要得到c <-> d和d <-> h作为两个分离的有向循环。

我不知道这个问题是否是多项式的。我看过一篇论文“枚举最小割和强连通子图”，似乎得出了这个问题是增量多项式的结论（我不知道这意味着什么），但是我无法从这篇文章中提取出一个算法。我也不确定最小强连通分量是否等同于我定义的最小循环。

有人知道这个问题的答案吗？

提前感谢！！！

- JRe

---

最短路径或带权弧的最小成本循环。 - kriss

Answer 1

如果我们正在寻找最短路径循环，那么似乎很容易。

• 对所有节点进行广度优先搜索，寻找从一个节点到其本身的最短路径。
• 如果找不到路径，则可以删除此节点，因为它不在任何循环中。
• 如果找到一条路径，则已经找到了其中一个最小循环（由于我们寻找最短路径，因此可以确保此循环不能是两个更短循环的并集）。
  • 将其中的所有节点合并为一个新节点，并根据需要调整边缘。

• 继续，直到没有节点了。

• 当您处理完所有节点（顶点）时，您就可以得到您要查找的最小循环...但有一个技巧。

如果一个环只使用初始集合中的节点表示，你可以保持它“原样”。但是你必须将“大节点”翻译为路径（循环之间的公共边），每个大节点可能会被几个这样的路径替换（对于一个不包含大节点本身的一级大节点至少有两个）。找到的环是按这样的方式构造的，以便您可以选择任何路径并仍然获得最小环集（不能通过联合两个其他环来获得任何环），但是存在几组可能的环。您可以添加一个约束条件，始终选择最短路径，但仍可能存在相同长度的路径。因此，这个问题的解决方案显然不是唯一的。

采用这种朴素方法，复杂度将是O（V·（E+V）），其中V是顶点数，E是边数。 O（E + V）来自广度优先搜索，最坏情况下您必须执行V次BFS。因此，它肯定是多项式或更好的。我相信我所描述的在平均情况下确实是O（log（V）·（E+V）），但我还没有证明它是否正确。

- kriss

---

这似乎很吸引人，但如果一个节点和它本身之间有多条最短路径，我该怎么办？ - JRe

任选其一，两者都是解决方案，且都是最小的。您也可以考虑枚举所有可能的解决方案，但这看起来是指数级的。我愿意使用C++和boost或Python实现此算法（为了好玩并检查它是否有效，这种练习对技能培训很有帮助）。在C++和Python之间有任何偏好吗？ - kriss

Answer 2

我们正在寻找所有的简单环路，而不仅仅是最短或最便宜的。（如果simple是正确的术语——我的意思是不相交的周期。）

下面是一个广度优先算法应该做的工作：

1.编号节点。 2.在每个节点上放置一个推销员并开始操作： - 如果推销员有选择要走哪条边，他会复制自己并走所有可能的方式。 - 当他到达一个节点时， - 如果它的编号比他起始的节点低，他就死了； - 如果这是他以前访问过的一个节点，他将记录该周期并死亡，从列表中删除冗余周期。

我不确定这个算法的复杂度，但看起来像O(EV²)。

编辑：

现在我想起来，你可以通过在编号最低的节点上开始，把复杂度降到O(EV)，当他的后代全部死亡时，从未访问过的最低编号的节点重新开始。重复直到所有节点都被访问。

- Beta

---

感谢大家的回答，我不确定这些算法是否能解决问题。事实是我看到了一篇论文（http://www.dis.uniroma1.it/~demetres/events/ads07/abstracts/Mehlhorn.pdf），正式描述了这个问题。问题的描述似乎与我的期望非常相似。在这篇论文中，描述了一些工作，显然最好的算法是|V|2*|A|，但编码似乎非常困难！我将尝试您的解决方案并查看结果...非常感谢 - JRe

Answer 3

也许列举独立循环的枚举会有所帮助？

我建议尝试以下步骤：

1. 首先，为了找出参与循环的顶点，请执行传递闭包。这是一个O（V^3）的算法。
2. 删除所有其他顶点。
3. 现在，剩下的图中存在完全独立循环覆盖（这是我的想法的弱点，我无法证明循环是独立的）
4. 它的解决方案是"二分图中的最大配对匹配"算法。

4.1.将图G中的每个顶点v转换为2个（v1和v2），并将它们放置在二分图G2的不同部分。

4.2.对于G中的每条边e（v，u），向G2的第1部分添加一条边到第2部分-e（v1，u2）。

4.3.在G2中查找最大配对匹配。它是G2边的子集。

5.该子集对应于G中一组最大（完整）的独立循环。

- Victor Sergienko

Answer 4

可能已经太晚回答了，但无论如何...

这个问题没有多项式解的原因非常简单：在（有向）图中可能存在指数级别数量的最小环。

考虑大小为n/2的n/2个大小为2的集合，并将它们循环排列：A_1, ..., A_{n/2}，并使用约定A_{n/2+1}=A_1。当且仅当两个顶点位于连续索引的集合中时（因此，通过上述约定，A_{n/2}中的元素也与A_1中的元素相连），才在两个顶点之间放置一条边。如果您对有向图而不是简单图感兴趣，请将边定向，使其始终指向具有更大索引的集合中的顶点，或者在A_{n/2}和A_1的情况下，从A_{n/2}中的顶点指向A_1中的顶点。

显然在这个长度为n/2的图中有2^{n/2}个最小循环，因为所有大小为n/2且恰好包含每个A_i中一个顶点的子集都是这样一个循环。如果你想用算法列出它们，那么该算法至少需要进行2^{n/2}步。

- APongracz