令 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' 中的一对边可能具有相同的起始顶点或相同的结束顶点。这与文献中使用的一些有向生成树的定义相冲突。
编辑：添加了与生成树相关的直观描述、背景信息和注释。