如何在无向图中找到反馈边集

Question

设 G = (V,E) 为一个无向图。若一个边集 F ⊆ E 满足 G 的每个环中至少包含一条 F 中的边，则称其为反馈边集。

(a) 假设 G 是无权图。设计一个高效的算法来寻找最小大小的反馈边集。

(b) 假设 G 是带正权重的无向图。设计一个高效的算法来寻找最小权重的反馈边集。

---

我的解决方案（需要建议）：

a) 最小大小反馈边集：由于图是无权的，我们可以使用 DFS。我们像往常一样从任何一个顶点开始 DFS。当遇到一条返祖边时，将其插入反馈边集。当 DFS 完成时，集合将是答案。

b) 最小权重反馈边集：由于图是加权的，我们可以使用 Kruskal 算法。但 Kruskal 通常从最小权重的边开始。如果我们可以取反所有边权重，并运行 Kruskal，每当我们得到一个连接同一连通分量的边时，我们就可以保存它在反馈边集中。最后，反转边权重。我建议反转边权重的原因是因为我们需要最小权重反馈集。使用取反后的权重，Kruskal 将从权重最小（实际上是最大）的边开始，并找到具有更小权重的相同连通分量的边。

可以有人告诉我这个解决方案是否正确吗？

- Jake

---

在解决方案A中，我们如何考虑两个环共享一条边的可能性？由于这条边承担了两个环的任务，因此这条边应该优先于任何一个环中的其他边。 - bytefire

@bytefire 菱形图有3个循环，而不是2个。最小尺寸反馈边集将为2，而不是1。选择还是不选择共享边都没有任何区别。 - nitely

这两个问题之间实际上存在一个众所周知的二元性，即图形拟阵和余图拟阵。 - Narek Bojikian

Answer 1

在具有正权重的有向加权图中找到最小权重的反馈边集：

通过取反权值，可以发现它等同于查找最大权重的反馈边集。 要找到最大权重的反馈边集，请使用Prim或Kruskal算法构建MST。然后取该MST的补集。

为什么这样做可行？ 这是基于以下观察结果：

如果存在一个循环，使得一条边在该循环中的所有其他边中具有最大权重，则该边不在任何MST中。 换句话说，如果对于每个包含该边的循环，它在该循环中的所有其他边中不是最大权重，则该边在某些MST中。

确实，假设我们有一个最大权重的反馈边集，并且存在一条边，使得存在一个循环，其中该边和另一条具有更大权重的边，那么用这条边替换该边将提供更大权重的反馈边集。

为了完整起见，以下是对该观察结果的证明：

<=）假设一条边在一个循环中具有最大权重。如果它在某个MST中，则用该循环中的另一条边替换该边将提供更小权重的MST。

=>) 假设对于每个包含给定边的循环，存在一条具有更大权重的边。如果它不在任何MST中，则将该边添加到MST中会导致MST中出现一个循环。然后从该循环中删除最大权重的边（与给定边不同），将提供更小权重的MST（并包括该给定边）。

- user3017842

---

使用 G' 表示取反权重后的图。G' 的最小生成树即为 G 的最大生成树。 - Jingguo Yao

Answer 2

是的，你的解决方案是正确的。无向图的最小权重反馈边集是最大权重生成森林的补集。所有生成森林具有相同的基数，因此在无权重情况下，任何生成森林（如通过DFS找到的）都可以使用。（证明草图：拟阵。）

反馈弧集确实是NP难问题，但这是无向图的情况。

- just keep walking

---

无向图的最小权重反馈边集是最大权重生成森林的补集。您能稍微解释一下这个观点吗？或者可能是发布一个链接。看到证明会很有趣。 - bytefire

Answer 3

这两个问题都是NP完全问题。因此，即使是近似高效（多项式时间）的解决方案也不太可能存在（http://en.wikipedia.org/wiki/Feedback_arc_set）。

如果您可以放宽应用程序中对严格最小解决方案大小的要求，则有其他启发式方法可用，但它们可能难以相互比较。

请注意，您可以轻松找到最小（而非最小）解决方案：按任意顺序遍历任何反馈边集的边，并立即删除冗余的边。一次遍历所有边就足够了，并使用例如DFS进行冗余测试。

- bennos

---

感谢@justkeepwalking指出这是无向图的情况...因此我的帖子忽略了这个问题的重点。 - bennos

最小权重反馈弧集不是NP难问题，可以通过使用Kruskal算法找到最大生成树来解决。这可以在多项式时间内完成。 - TomR

Answer 4

对于任何反馈边，该图的补图必须是原始图的生成森林。也就是说，补图不包含任何环，这是非常明显的。

问题a：
对于最小大小的反馈边集，这等价于找到最大大小的生成森林。因此，我们可以简单地使用DFS来查找图的每个连通分量的生成树并取补集。然后我们得到一个最小大小的反馈边。实际上，我认为DFS并不是必要的，只要我们能够为每个连通分量找到一棵生成树即可。
问题b：
要找到最小权重反馈边集，这等价于找到最大权重生成森林。然后我们可以使用Kruskal算法或Prim算法来找到每个连通分量的最大生成树。然后取补集，我们将得到一个最小权重反馈集。

- Eric mingjie

Answer 5

你的解决方案A）不会起作用，因为你没有提供任何逻辑来决定边缘是否具有“后向”属性。

你的解决方案B）不会起作用，因为Kruskal并不寻找反馈集，而是寻找最小加权覆盖树。一个很好的例子是K4图，说明最小加权树不一定包括反馈边集。

- Pyra

---

至于A部分的答案，对于无向图的DFS将边分类为树边和反向边 - 这是关于DFS的一个非常基本的事实。 - Jake

没事，我回答得太快了。 您确实可以使用深度优先搜索来检测循环，当它遇到一个已经访问过的节点时。但是，您如何选择该循环的哪个边将成为您的反馈边集的一部分呢？ 您可以选择使用DFS，并选择任何导致已经访问过的节点的边（而不仅仅是指向祖先的边）。这肯定会给您一个反馈边集。但是，E也是一个反馈边集。 - Pyra

你要找的是最小尺寸的反馈边集。DFS无法提供逻辑的一个很好的例子是由两个具有一个共同边缘的循环组成的图形。没有办法让你的DFS仅使用您在开头消息中提供的逻辑或我在上面的答案中提供的逻辑标记仅有一个公共边缘。甚至有些情况下，这条边 不会 成为给定解决方案的一部分。（抱歉，分成两部分，字符不够） - Pyra

对于由两个有共同边的环组成的图，这个公共边不一定是最小反馈边集的一部分。原因是这个图总共包含了3个环，而单独的这条共同边并不能构成一个反馈边集。 - Hartmut Klauck