graph-algorithm - 如果降低特定的边缘成本，判断 MST 是否会改善的简单方法？

Question

G是一个在所有边上具有正成本的无向连通图。给定的是e成本严格大于 10 的边。我们需要回答如果成本e减少 10，MST 成本是否会提高。

我知道一个解决方案，它涉及生成一个只有边的新图cost<cost(e)-10。这个更简单的解决方案有什么问题：取一个e's vertices v。找到 的最小成本边事件v。现在降低e成本并v再次找到最低成本边缘事件。如果有变化，则意味着prim会找到更好的MST，并且成本会有所提高。如果不是，则意味着 prim 将找到相同的 MST，并且成本保持不变。

这个逻辑有什么问题？

与修改边更新最小生成树有关

标签： graph-algorithmminimum-spanning-treekruskals-algorithmprims-algorithm

Answer 1

我不认为你的解决方案是正确的。

考虑下图 G = (V, E), V = {a, b, c, d, e}, E = {ab, bc, cd, de, ae, bd} 并且各自的权重是 {5, 10 , 10, 5, 17}。

通过运行 Kruskal 或 Prim，我们发现我们的 MST 是 {ab, bc, cd, de}，他的权重是 30。

现在，让我们将边 bd 的权重从 17 减少到 7，并再次检查边。

使用 G' 运行 Prim 或 Kruskal 将输出一个重 27 的 MST（实际上我们有 2 个这样的 MST {ab, bd, de, cd} 和 {ab, bd, de, bc}）。

但是如果我们使用你的算法，我们会得到完全相同的树，因为当我们检查节点 b 或 d 时，边 bd 不是与这些节点中的任何一个相邻的最轻的边。