minimum-spanning-forest

1热度

1回答

最大生成树查找覆盖每个周期的最小边集

我得到以下任务：给定一个图G：=（V，E）并且任意多个周期。什么是最小边集，以便对于图中的每个循环，集合中至少包含一个边 - 或者更精确地说，这些边的权重总和是多少。 我的方法非常简单：我在图上计算了一个最大跨度森林，排除了每条边，并将剩余边缘作为结果。这个想法如下：由于每个生成树都没有周期，所以我永远不会删除整个周期，因此不会有任何我没有覆盖的周期。此外，我也无法删除图G中的任何其他边，因为如果

algorithm graph minimum-spanning-forest 2017-11-11

---