在向图表添加新边缘后查找新的最小生成树

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 （按选择顺序-weight （a （i））<=权重（a（i + 1）））。

现在让我们考虑如何在输入E'= EU {e}的情况下给出Kruskal算法的行为。令i = min {i：weight（e）<weight（a（i））}。首先，算法决定选择边[a（1），...，a（i-1）]（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）]。但是，在寻找G的 MST时，Kruskal的算法没有做到这一点。这导致了矛盾。

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）考虑后，分成相连分量（由所选边的集合确定）的方式是相同的。因此，在处理后，两种情况下的（k + 1）算法将以相同的方式进行。