最大生成树找到覆盖每个循环的最小边集
Maximal Spanning Tree to find a minimal set of edges that cover each cycle
我接到了以下任务：给定一个具有任意多个循环的图 G := (V, E)。最小边集是多少，以便对于图中的每个循环，该集中至少包含一条边 - 或者更准确地说，这些边的权重之和是多少。
我的方法非常简单：我计算了图上的最大跨度森林，排除了每条边并声明了剩余的边作为结果。这个想法如下：由于每个生成树都没有循环，所以我永远不会删除整个循环，因此不会有任何我没有涵盖的循环。此外，我也无法删除图 G 中的任何其他边，因为如果我这样做，我将删除一个循环，因此结果不会涵盖所有循环。因此我断定我的方法是正确的。
不过好像不是这样的。任何人都可以启发我哪里出错了吗？我想不出一个反驳我的方法的例子。
这可以解决为 set covering problem。
索引弧 1...m。让 j 指代任意弧。
索引周期 1...n。让我参考任意循环。
如果第 j 个弧是第 i 个循环的一部分，则指示变量 a_{ji} = 1。 0 否则。
让 x_j = 1 如果第 j 个弧被 selected 作为你的解决方案的一部分。
您想尽量减少弧的数量 select。
所以，最小化 \sum_{j=1}^{m} x_j
限制条件是您的 selected 弧应该覆盖所有循环。
特别是，对于任何循环 i，您至少需要它的一条边 selected。
因此，按如下方式建模。
对于每个 i，\sum_{j=1}^{m} a_{ji}x_{j} >= 1.
会有n个这样的约束，每个i一个。
另一个约束是每个 x_{j} 要么是 0 要么是 1。
如果您正在寻求解决加权版本，那么给定弧 j 的权重 c_j，objective 需要更改为
\sum_{j=1}^{m} c_j x_j
我接到了以下任务：给定一个具有任意多个循环的图 G := (V, E)。最小边集是多少，以便对于图中的每个循环，该集中至少包含一条边 - 或者更准确地说，这些边的权重之和是多少。
我的方法非常简单：我计算了图上的最大跨度森林，排除了每条边并声明了剩余的边作为结果。这个想法如下：由于每个生成树都没有循环，所以我永远不会删除整个循环，因此不会有任何我没有涵盖的循环。此外，我也无法删除图 G 中的任何其他边，因为如果我这样做，我将删除一个循环，因此结果不会涵盖所有循环。因此我断定我的方法是正确的。
不过好像不是这样的。任何人都可以启发我哪里出错了吗？我想不出一个反驳我的方法的例子。
这可以解决为 set covering problem。
索引弧 1...m。让 j 指代任意弧。
索引周期 1...n。让我参考任意循环。
如果第 j 个弧是第 i 个循环的一部分，则指示变量 a_{ji} = 1。 0 否则。
让 x_j = 1 如果第 j 个弧被 selected 作为你的解决方案的一部分。
您想尽量减少弧的数量 select。
所以，最小化 \sum_{j=1}^{m} x_j
限制条件是您的 selected 弧应该覆盖所有循环。
特别是，对于任何循环 i，您至少需要它的一条边 selected。
因此，按如下方式建模。
对于每个 i，\sum_{j=1}^{m} a_{ji}x_{j} >= 1.
会有n个这样的约束，每个i一个。
另一个约束是每个 x_{j} 要么是 0 要么是 1。
如果您正在寻求解决加权版本，那么给定弧 j 的权重 c_j，objective 需要更改为
\sum_{j=1}^{m} c_j x_j