如何删除未加权有向图中的循环，以使边的数量最大化？ [英] How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

问题描述

让G是一个包含循环的未加权有向图。我正在寻找一种算法，该算法可以查找/创建所有非循环图G'，该图由G中的所有顶点和G的边的子集组成，正好足以使G'变为非循环。

更正式：所需算法消耗G并创建一组非循环图S，其中S中的每个图G'满足以下属性：

1. G'包含G的所有顶点。


2. G'包含G的边的子集，这样G'是非循环的。


3. G'的边数最大。这意味着：没有G''满足属性1和2，因此G''包含更多的边，那么G'和G''是无环的。

背景：原始图形G对元素之间的成对排序建模。由于图形中的循环，不能将其用作对所有元素的排序。因此，最大无环图G'应该为该排序建模一个最佳可能的近似值，尝试尽可能多地考虑成对排序关系。

，可以删除所有可能的边组合，并在每次删除后检查非循环性。在这种情况下，会有一个强烈变化的分支树，这意味着时间和空间的复杂性。

注意：问题可能与生成树有关，您可以定义G'图是一种有向生成树。但请记住，在我的情况下，G’中的一对边可能具有相同的起点或终点。这与文学中使用的定向生成树的某些定义相冲突。

编辑：添加了与生成树相关的直观描述，背景信息和注释。

解决方案

此该问题称为反馈弧集。由于它是NP难解的，因此不太可能找到可扩展的快速算法。但是，如果您的实例很小，则B. Schwikowski和E.Speckenmeyer的关于枚举反馈问题的所有最小解一文中的算法可能会起作用。

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:

1. G' contains all vertices of G.
2. G' contains a subset of edges of G, such that G' is acyclic.
3. 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.

解决方案

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.

这篇关于如何删除未加权有向图中的循环，以使边的数量最大化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！