algorithm - 如果删除一条边，如何从旧 MST 更新 MST

Question

我是学算法的，见过这样的习题

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

我将不胜感激。

Answer 1

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

Premise P: Select minimum weight edge (x,y) from G - (u,v) that reconnects A and B. Then T' = A + B + (x,y) is a MST of G - (u,v).

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。