algorithm - 如何找到权重不超过 k 的反馈集

Question

任何无向加权图的反馈集都是边的子集，这样在删除子集中的边之后，剩余的图是无环的。

给定 G = (V, E)，一个无向加权图和一个整数 k，我如何确定是否存在总权重不超过 k 的反馈集？

谢谢！

标签： algorithmgraphgraph-algorithmdepth-first-search

Answer 1

最小反馈集永远不会包含断开图的两个组件的边，因此删除反馈集不会改变连接的组件，但它会使每个连接的组件变成非循环的。

如果一个无向图是连通的且无环的，那么它就是一棵树，所以：

对于图中的每个连接组件，找到最大权重生成树。您可以通过否定所有权重来使用任何最小权重生成树算法。

不在任何最大权重生成树中的边是最小权重反馈集。

为了找到所有最大权重树，我建议在整个图上使用 Kruskal 算法，边按权重降序排序，因为它会一次找到它们。然后只需选择不在任何树中的所有边。