我得到以下任务：给定一个图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}^{米} x_j
的约束是，所选的弧应涵盖所有周期。
特别是，对于任何周期我都希望至少选择其中一个边。
因此，建模如下。
对于每个i，\ sum_ {J = 1}^{米} A_ {ジ} X_ {Ĵ}> = 1
将有N个这样的约束，一个对于每个i。
另一个约束是，每个X_ {Ĵ}是0或1。
如果你正在寻找解决加权的版本，那么给定弧j具有重量C_J，需要将目标改变至
\ sum_ {J = 1}^{M} C_J x_j
我深知，它可以以这种方式实现，但由于集合覆盖问题是NP完全问题我是绝对的计算没有兴趣的是办法。我有点在我的模型中寻找错误，而不是对于任何大量的边缘几乎无法解决的问题。 –