有向图中要删除的边的最小数目是多少，才能删除所有圈？

Question

我们必须找到有向图中要删除的最小边数，才能删除所有循环。在这里输入图像描述。

例如：-在这个图中，有3个循环：

1) 0-1-2-0

2) 0-2-0

3) 3-3

有两种可能的组合可以删除所有循环：

1)删除边缘2-0和3-3。

2)删除0-2，1-2和3-3的边缘.

在第一种情况下，我们必须删除2条边，在第二种情况下，我们必须删除3条边。

第一种组合是解决办法。

Answer 1

这个问题名为http://en.wikipedia.org/wiki/Feedback_arc_set问题，是众所周知的.这个问题的决策版本说:给定一个图G和一个参数k，我们可以通过从它中删除一些至多k弧的集合来打破G中的所有循环吗？注意，与往常一样，决策版本并不比寻找最小反馈集的计算版本更难。

上述问题的决策版本是NP-完全的.事实上，这是Richard的21个NP-完备问题之一。也就是说，除非NP崩溃到P--人们普遍认为不太可能--这个问题就不允许采用多项式时间算法。你可以从维基百科的网页上查找细节。