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

Question

G是一个无向连通图，它在所有边上都具有正代价。给出了成本严格大于10的边缘e。如果e的成本降低10，我们需要回答它的成本是否会提高。

我知道一种解决方案，它涉及到用cost<cost(e)-10生成一个只有边的新图。这个简单得多的解决方案有什么问题:以e的一个顶点v为例。找到v的最小成本边缘事件。现在降低e的成本，并再次找到v的最小成本边缘事件。如果有变化，这意味着prim会找到更好的MST，成本也会得到改善。如果没有，这意味着prim会找到相同的MST，成本保持不变。

这逻辑怎么了？

与Update minimum spanning tree with modification of edge相关

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 (实际上我们有两个这样的MSTs {ab，bd，de，cd}和{ab，bd，de，bc})。

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

Answer 2

让我们G = (V, E)是一个图。

定义

其中w(<u,v>)是<u,v>的权重。

引理1

让我们让G是一个图，v是G的一个顶点，e是G的一个边缘到v。如果是w(e) = C(v)，那么e属于G的某些MST。

诚然，如果C(v)值在e的成本被10降低时被改变，那么如果10通过引理1降低e的成本，那么e的成本就会提高。

上半场没问题。让我们看一下第二部分。

如果不是

，这意味着prim会找到相同的MST，并且成本保持不变。

通用解释

前面的引文错误地暗示引理1的逆序是真的(e属于G的一些MST，然后是w(e) = C(v))，因为它声称如果通过10和w(e) != C(v)降低e的成本，那么MST成本就会被保留，这意味着e不属于G的任何MST。

简短解释:反例

让我们使用加权函数G = ({1, 2, 3, 4}, {<1, 2>, <1, 3>, <2, 4>, <3, 4>, <1, 4>})，w(<1, 2>) = 1, w(<1, 3>) = 3, w(<2, 4>) = 3, w(<3, 4>) = 1, w(<1, 4>) = 12和e = <1, 4>。

在降低了e的代价后，我们知道了C(1) = C(4) = 1 != w(e)算法，提出的算法是："prim会找到相同的MST，代价保持不变“。

当e的成本被10降低时，让我们检查G的MST成本是否有下降

用e：10：5降低10：5成本前的MST成本

用10：4降低10：4成本后的MST成本

由于MST成本降低了，那么这种索赔(引用的)是错误的，并且提出的算法不起作用。

注意:无论使用哪种MST算法，该算法都是错误的，因为防御性仅依赖于MST属性。