如果一条边被删除，如何从旧的 MST 更新 MST

Question

我正在研究算法，我见过这样的练习

我可以用指数时间克服这个问题，但是。我不知道如何证明这个线性时间 O(E+V)

我将不胜感激任何帮助。

Answer 1

设 G 为嵌入最小生成树 T 的图；设 A 和 B 是从 T 中删除 (u,v) 后剩下的两棵树。

前提 P：从重新连接 A 和 B 的 G - (u,v) 中选择最小权重边 (x,y)。然后 T' = A + B + (x,y) 是 G - (u,v) 的 MST .

P 的证明：很明显 T' 是一棵树。假设它不是最​​小值。然后会有一个更小重量的 MST——称之为 M。要么 M 包含 (x,y)，要么不包含。

如果 M 包含 (x,y)，那么它必须具有 A' + B' + (x,y) 的形式，其中 A' 和 B' 是最小权重树，它们跨越与 A 和 B 相同的顶点。这些不能权重小于 A 和 B，否则 T 不会是 MST。所以M毕竟不小于T'，矛盾；M 不可能存在。

如果 M 不包含 (x,y)，则在 M 中存在从 x 到 y 的其他路径 P。P 的一条或多条边从 A 中的一个顶点传递到 B 中的另一个顶点。称这样的边为 c。现在，c 的权重至少是 (x,y) 的权重，否则我们会选择它而不是 (x,y) 来形成 T'。注意 P+(x,y) 是一个循环。因此，M - c + (x,y) 也是一棵生成树。如果 c 的权重大于 (x,y)，那么这棵新树的权重将小于 M。这与 M 是 MST 的假设相矛盾。再一次，M 不能存在。

由于在任何一种情况下，M 都不存在，T' 必须是 MST。QED

算法 遍历 A 并将其所有顶点着色为红色。同样将 B 的顶点标记为蓝色。现在遍历 G - (u,v) 的边列表以找到连接红色顶点和蓝色顶点的最小权重边。新的 MST 就是这条边加上 A 和 B。