枚举有向图的所有最小有向循环
我有一个有向图，我的问题是枚举该图的所有最小（无法构造为其他循环并集的循环）有向循环。这与 Tarjan 算法的输出不同。例如，对于此维基百科页面处的有向图，我想得到 c < -> d和d<-> h 作为两个独立的有向循环。
我不知道这个问题是否是多项式。我读过一篇论文“枚举最小二切和强连通子图”，似乎得出的结论是这个问题是增量多项式（我不知道它意味着什么），但我无法为本文提取算法。我也不确定最小的强连通分量是否相当于我定义的最小循环。
有人知道这个问题的答案吗？
提前致谢！！！
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the Tarjan algorithm outputs. For instance, for the directed graph at this wikipedia page, I would like to get c <-> d and d <-> h as two separated directed cycles.
I don't if this problem is polynomial or not. I ran over a paper "Enumerating Minimal Dicuts and Strongly Connected Subgraphs" that seems to conclude that this problem is incremental polynomial (I don't know what it means), but I am unable to extract an algorithm for this article. I am also not sure if a minimal strongly connected component is equivalent to a minimal cycle as I define it.
Does someone knows the answer to this problem?
Thanks in advance!!!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果我们正在寻找最短的路径周期，这似乎很容易。
继续下去，直到不再有节点。
当你处理完所有节点（顶点）时，你会得到你正在寻找的最小周期...但是有一个技巧。
当你
如果仅使用初始集中的节点来表达循环，则可以将其保持“原样”。但是你必须将“大节点”转换为路径（循环之间的公共边），并且每个大节点都可以被多个这样的路径替换（对于级别1的大节点至少有2个，即不包含大节点本身）。找到的循环的构造方式使得您可以选择任何路径，并且仍然获得最小的循环集（没有循环可以完成其他两个循环的并集），但是有几个可能的这样的集合。您可以添加约束以在大节点中选择路径时始终采用最短路径，但仍然可以存在相同长度的路径。所以这个问题的解显然不够唯一。
使用这种简单的方法，复杂度将为 O(V.(E+V))，其中 V 是顶点数，E 是边数。 O(E+V) 来自广度优先，最坏的情况是你必须执行 V 次 BFS。因此它绝对是更好的多项式。我相信我所描述的在平均情况下确实是 O(log(V).(E+V)) ，但我还没有证明它（如果它是真的）。
If we are looking for the shortest path cycle, it seems easy enough.
Go on until there is no node any-more.
When You you have treated all nodes (vertexes) you have the minimal cycles you where looking for... but there is a trick.
If a cycle is expressed using only nodes from the initial set you can keep it "as is". But you have to translate "big nodes" to paths (common edges between cycles) and every big nodes may be replaced by several such path (at least 2 for a big node of level-1, that is that does not contains big nodes itself). The cycles found are constructed in such a way that you can choose any path and still get a minimal cycle set (no cycle can be get doing the union of two others), but there is several possible such sets. You can add a constraint to always take a shortest path when selecting a path in a big node, but there still can be paths of the same length. So the solution of this problem is clearly enough not unique.
With this naive approach complexity would be O(V.(E+V)) where V is the number of vertexes and E the number of edges. O(E+V) comes from breadth first and at worst you have to perform a BFS V times. Hence it is definitely polynomial of better. I believe what I described is really O(log(V).(E+V)) in the average case, but I didn't prove it yet (if it's true).
我们正在寻找所有简单的周期，而不仅仅是最短或最便宜的周期。 （如果简单是正确的术语——我指的是不自相交的循环。）
这是一个可以完成这项工作的广度优先算法：
对节点进行编号。
在每个节点上放置一名推销员并开始操作：
如果推销员可以选择采取哪种优势，他就会模仿自己并采取所有可能的方式。
当他到达某个节点时，
如果它的数字比他开始时的数字低，他就会死亡；如果它是他在记录该周期并死亡之前访问过的数字。从列表中删除多余的循环。
我不确定这个的复杂性，但它看起来像 O(EV^2)。
编辑：
现在我想起来了，您可能可以通过从编号最低的节点上的一名推销员开始来达到 O(EV)。当他的所有后代都死了时，从尚未访问过的最低编号节点上的推销员重新开始。重复直到所有节点都被访问过。
We're looking for all simple cycles, not just the shortest or cheapest. (If simple is the right term-- I mean cycles that do not self-intersect.)
Here's a breadth-first algorithm that should do the job:
Number the nodes.
Place a salesman on every node and begin the operation:
If a salesman has a choice of which edge to take, he copies himself and goes all possible ways.
When he arrives at a node,
if it has a lower number than the one he started on he dies, and if it's one he's visited before he records that cycle and dies. Remove the redundant cycles from the list.
I'm not sure of the complexity of this, but it looks like O(EV^2).
EDIT:
Now that I think of it, you can probably get to O(EV) by starting with one salesman on the lowest numbered node. When all his descendents are dead, start again with a salesman on the lowest numbered node that has not yet been visited. Repeat until all nodes have been visited.
也许枚举独立循环会有所帮助？
我会尝试以下操作。
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 中独立循环的最大（完整）集。
Maybe an enumeration of INDEPENDENT cycles will help?
I'd try the following.
4.1. Turn each vertex v in your graph (G) into 2 (v1 and v2), place each in different parts of bipartitive graph (G2).
4.2. For each edge e(v,u) in G, add an edge from 1st part of G2 to 2nd - e(v1,u2).
4.3. Find a maximal pair matching in G2. It's a subset of G2 edges.
5 That subset corresponds to a maximal (full) set of independent loops in G.
这可能已经太晚了，但无论如何......
该问题没有多项式解，原因非常简单：（二）图中可能存在指数数量的最小循环。
考虑
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}步骤。This is probably too late to answer, but anyway...
The problem has no polynomial solution for a very simple reason: it is possible that there are exponentially many minimal cycles in a (di)graph.
Consider
n/2sets of size 2, and arrange them cyclically:A_1, ..., A_{n/2}, and use the conventionA_{n/2+1}=A_1. Put an edge between two vertices if and only if they lie in sets of consecutive indices (so elements inA_{n/2}are also linked to elements inA_1, by the above convention). If you are interested in digraphs rather than simple graphs, direct the edges so that it always points towards the vertex that lies in the set with the bigger index, or in case ofA_{n/2}andA_1, it point from vertices inA_{n/2}towards those inA_1.Clearly there are
2^{n/2}minimal cycles in this graph of lengthn/2, because all subsets of sizen/2that contain exactly one vertex in eachA_iis such a cycle. If you want to list them all with an algorithm, that algorithm must make at least2^{n/2}steps.