algorithm - 最大生成树找到覆盖每个循环的最小边集

Question

我得到了以下任务:给定一个具有任意多个循环的图 G := (V, E)。最小边集是多少，以便对于图中的每个循环，该集中至少包含一条边 - 或者更准确地说，这些边的权重之和是多少。

我的方法非常简单:我计算了图上的最大生成森林，排除了每条边，并宣布剩余边作为结果。这个想法如下:由于每个生成树都没有循环，所以我永远不会删除整个循环，因此不会有任何我没有涵盖的循环。此外，我也无法删除图 G 中的任何其他边，因为如果我这样做，我将删除一个循环，因此结果不会涵盖所有循环。因此我断定我的方法是正确的。

不过好像不是这样的。任何人都可以启发我哪里出错了吗？我想不出一个反驳我的方法的例子。

Answer 1

这可以解决为 set covering problem .

索引弧 1...m。令j指代任意弧。

索引循环 1...n。让我指的是任意循环。

如果第 j 个弧是第 i 个循环的一部分，则指示变量 a_{ji} = 1。 0 否则。

如果第 j 个弧被选为您的解决方案的一部分，则令 x_j = 1。

您想尽量减少选择的圆弧数。

因此，最小化\sum_{j=1}^{m} x_j

约束是您选择的弧应该覆盖所有循环。

特别地，对于任何循环 i，您希望至少选择它的一条边。

因此，按如下方式建模。

对于每个 i，\sum_{j=1}^{m} a_{ji}x_{j} >= 1。

将有 n 个这样的约束，每个 i 一个。

另一个约束是每个 x_{j} 要么是 0 要么是 1。

如果你正在寻求解决加权版本，那么给定弧 j 的权重为 c_j，目标需要更改为

\sum_{j=1}^{m} c_j x_j