algorithm - 在将新边添加到图中后查找新的最小生成树

Question

令 G = (V, E) 为加权、连通且无向图，令 T 为最小生成树。令 e 为不在 E 中的任何边（并且具有权重 W(e)）。证明或反证：TU {e} 是一个边集，包含 G' = (V, EU {e}) 的最小生成树。

好吧，这对我来说听起来很真实，所以我决定证明这一点，但我每次都卡住了......

例如，如果 e 是具有最小权重的新边，谁能向我们保证 T 中的边没有以错误的方式选择，这会阻止我们在没有 E 中其他边的“帮助”的情况下获得新的最小权重-T？

我会很感激任何帮助，在此先感谢。

Answer 1

让[a(1), a(2), ..., a(n-1)]是从E中选择的边序列，以通过 Kruskal 算法构造G的MST （按照它们被选择的顺序 -权重（a (i)) <= 重量(a(i + 1)) )。

现在让我们考虑一下 Kruskal 算法在输入E' = EU {e}时的表现。让i = min{i: weight(e) < weight(a(i))}。首先算法决定选择边[a(1), ..., a(i - 1)]（e还没有被处理，所以它的行为是一样的）。然后它需要决定e - 如果e被删除，E' 的解决方案将与E相同。所以让我们假设算法选择的前i个边是[a(1), ..., a(i - 1), e] - 我将把这个新序列称为 a'。算法继续 - 只要其以下选择（对于 j > i）满足a'(j) = a(j - 1)我们很酷。有两种情况会打破如此大的连胜（假设在索引k + 1处出现连胜）：

1) 算法选择一些不在T中的边 e' ，并且weight(e') < weight(a(k+1))。现在一个'序列是：

[a(1), ..., a(i-1), e, a(i), a(i+1), ..., a(k-1), a(k), e']

但是，如果可以将e'附加到此列表，则也可以将其附加到[a(1), ..., a(k-1), a(k)]。但是 Kruskal 的算法在为G寻找 MST 时并没有这样做。这导致矛盾。

2）礼貌选择的算法：

[a(1), ..., a(i-1), e, a(i), a(i+1), ..., a(k-1), a(k)]

但决定放弃边缘a(k+1)。但是如果e不存在于列表中，算法将决定附加a(k+1)。这意味着在图(V, {a(1), ..., a(k)}) 中，边a(k+1)将连接与边e相同的组件。这意味着在考虑G和G'的算法边a(k + 1)之后，划分为连通分量（由一组选定边确定）是相同的。因此，在处理后，a(k+1)算法在两种情况下都将以相同的方式进行。

Answer 2

当将一条边添加到图中而不添加节点时，该边会在图的最小生成树中创建一个循环，循环长度可能从 2 到 n 变化，其中 n = 图中的节点数。T = G 的最小生成树现在要找到 (T + added edge) 的 MST，我们只需从该循环中删除一条边 .. 所以删除具有最大权重的边。

所以 T' 总是来自 TU {e}。

如果您认为这并不能证明新的 MST 将是 TU {e} 的边集，那么请分析 Kruskal 算法以获取新图。即，如果 e 具有最小权重，则必须根据 Kruskal 算法为 MST 选择它，如果它是最小的，则不能从循环中删除。