如何删除未加权有向图中的循环，以使边数最大化？
令 G 为包含环的未加权有向图。我正在寻找一种算法，它可以找到/创建所有非循环图 G'，由 G 中的所有顶点和 G 的边子集组成，足够小以使 G' 非循环。
更正式：所需的算法消耗 G 并创建一组非循环图 S，其中 S 中的每个图 G' 满足以下属性：
- G' 包含 G 的所有顶点
- 。 G' 包含 G 的边的子集，使得 G'是非循环的。
- G' 的边数最大化。这意味着：不存在满足性质 1 和 2 的 G''，使得 G'' 包含的边数多于 G' 和 G'' 是无环的。
背景：原始图 G 对元素之间的成对排序进行建模。由于图中存在循环，因此不能将其用作对所有元素的排序。因此，最大无环图 G' 应该对该排序建立尽可能最好的近似模型，尝试尽可能多地尊重成对排序关系。
在一种简单的方法中，可以删除所有可能的边缘组合，并在每次删除后检查非循环性。在这种情况下，存在一个强分支的变化树，这意味着时间和空间复杂度很差。
注意：问题可能与生成树有关，您可以将 G' 图定义为一种有向生成树。但请记住，在我的场景中，G' 中的一对边可能具有相同的起始或相同的结束顶点。这与文献中使用的有向生成树的一些定义相冲突。
编辑：添加了与生成树相关的直观描述、背景信息和注释。
Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' acyclic.
More formal: The desired algorithm consumes G and creates a set of acyclic graphs S, where each graph G' in S satisfies following properties:
- G' contains all vertices of G.
- G' contains a subset of edges of G, such that G' is acyclic.
- The number of edges of G' is maximised. Which means: There is no G'' satisfying properties 1 and 2, such that G'' contains more edges then G' and G'' is acyclic.
Background: The original graph G models a pairwise ordering between elements. This can't be exploited as an ordering over all elements due to cycles in the graph. The maximal acyclic graphs G' therefore should model a best-possible approximation to this ordering, trying to respect as much of the pairwise ordering relation as possible.
In a naive approach, one could remove all possible combinations of edges and check for acyclicity after each removal. In this case there is a strongly branching tree of variations meaning bad time and space complexity.
Note: The problem may be related to a spanning tree, and you could define the G' graphs as a kind of directed spanning tree. But keep in mind that in my scenario a pair of edges in G' may have the same starting or the same ending vertex. This conflicts with some definitions of directed spanning trees used in literature.
EDIT: Added intuitive description, background information and note related to spanning trees.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个问题称为反馈弧集。由于它是 NP 困难的，因此您不太可能找到可扩展的快速算法。然而，如果您的实例很小，那么诸如 B. Schwikowski 和 E. Speckenmeyer 所著的论文“枚举反馈问题的所有最小解决方案”中的算法可能会起作用。
This problem is called Feedback Arc Set. Since it is NP-hard, it is unlikely that you will find a scalable fast algorithm. However, if your instances are small, then algorithms such as the one from the paper “On enumerating all minimal solutions of feedback problems” by B. Schwikowski and E. Speckenmeyer might work.