如果特定的边缘成本降低，判断 MST 是否会改善的简单方法？
simple way to tell if MST will improve if a specific edge cost is reduced?
G 是所有边上成本均为正的无向连通图。给定边e，其成本严格大于10。我们需要回答如果e的成本降低10，MST成本是否会提高。
我知道一个解决方案，它涉及生成一个新图，该图只包含 cost<cost(e)-10 的边。这个简单得多的解决方案有什么问题：
取 e 的顶点之一 v。找到 v 的最小成本边。现在减少 e 的成本并再次找到关联到 v 的最小成本边缘。如果有变化，就意味着 prim 会找到更好的 MST，成本也会降低。如果不是，这意味着 prim 会找到相同的 MST，并且成本保持不变。
这个逻辑有什么问题？
与Update minimum spanning tree with modification of edge相关
我认为您的解决方案不正确。
考虑下图 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 不是与这些节点中的任何一个相邻的最轻的边。
让我们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 时发生变化，那么如果 e 的成本是通过引理 1.
减少 10
上半场还好。让我们来看看第二部分。
If not, it means that prim would find the same MST and the cost stays the same.
一般说明
前面提到的引用错误地暗示引理 1 的逆命题是真的（e 属于 G 的某个 MST 然后 w(e) = C(v)）因为它声称如果我们减少 e 的10 和 w(e) != C(v) 的成本然后保留 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 之前的 MST 成本：5
将 e 的成本降低 10 后的 MST 成本：4
由于 MST 成本有所降低，因此这种说法（引用一个）是错误的，建议的算法不起作用。
注意：无论使用哪种MST算法，该算法都是错误的，因为反证明仅依赖于MST属性。
G 是所有边上成本均为正的无向连通图。给定边e，其成本严格大于10。我们需要回答如果e的成本降低10，MST成本是否会提高。
我知道一个解决方案，它涉及生成一个新图，该图只包含 cost<cost(e)-10 的边。这个简单得多的解决方案有什么问题：
取 e 的顶点之一 v。找到 v 的最小成本边。现在减少 e 的成本并再次找到关联到 v 的最小成本边缘。如果有变化，就意味着 prim 会找到更好的 MST，成本也会降低。如果不是，这意味着 prim 会找到相同的 MST，并且成本保持不变。
这个逻辑有什么问题？
与Update minimum spanning tree with modification of edge相关
我认为您的解决方案不正确。
考虑下图 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 不是与这些节点中的任何一个相邻的最轻的边。
让我们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 时发生变化，那么如果 e 的成本是通过引理 1.
10
上半场还好。让我们来看看第二部分。
If not, it means that prim would find the same MST and the cost stays the same.
一般说明
前面提到的引用错误地暗示引理 1 的逆命题是真的（e 属于 G 的某个 MST 然后 w(e) = C(v)）因为它声称如果我们减少 e 的10 和 w(e) != C(v) 的成本然后保留 MST 成本，这意味着 e 不属于 G.
简短说明：一个反例
让我们 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 之前的 MST 成本：5
将 e 的成本降低 10 后的 MST 成本：4
由于 MST 成本有所降低，因此这种说法（引用一个）是错误的，建议的算法不起作用。
注意：无论使用哪种MST算法，该算法都是错误的，因为反证明仅依赖于MST属性。