我得到了以下任务:给定一个具有任意多个循环的图 G := (V, E)。最小边集是多少，以便对于图中的每个循环，该集中至少包含一条边 - 或者更准确地说，这些边的权重之和是多少。
我的方法非常简单:我计算了图上的最大生成森林，排除了每条边，并宣布剩余边作为结果。这个想法如下:由于每个生成树都没有循环，所以我永远不会删除整个循环，因此不会有任何我没有涵盖的循环。此外，我也无法删除图 G 中的任何其他边，因为如果我这样做，我将删除一个循环，因此结果不会涵盖所有循环。因此我断定我的方法是正确的。
不过好像不是这样的。任何人都可以启发我哪里出错了吗？我想不出一个反驳我的方法的例子。
最佳答案
这可以解决为 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
关于algorithm - 最大生成树找到覆盖每个循环的最小边集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47238530/