Search for a new minimum spanning tree after adding a new graph to the chart

Question

Let G = (V, E) be a weighted, connected, and undirected graph, and T a minimal spanning tree. Let e ​​be any edge not in E (and has weight W (e)). Prove or disprove: TU {e} is the set of edges containing the minimal spanning tree G '= (V, EU {e}).

Well, that sounds believable to me, so I decided to prove it, but I just got stuck every time ...

For example, if e is a new edge with a minimum weight that can promise us that the edges in T were not chosen in a bad way, what would prevent us from getting a new minimum weight without the “help” of other edges in E - T?

Any help would be appreciated. Thanks in advance.

Answer 1

Let [a (1), a (2), ..., a (n-1)] be a sequence of edges selected from E for constructing an MST group G by the Kruskal algorithm (in the order of their choice, weight (a (i) ) <= weight (a (i + 1))).

Now we will consider how the Kruskal algorithm behaves as an input E '= EU {e}. Let i = min {i: weight (e) weight (a (i))}. First, the algorithm decides to select the edges [a (1), ..., a (i - 1)] (e has not yet been processed, so it behaves the same). Then we need to decide that e - if e is omitted, the solution for E 'will be the same as for E. So, let the first i edges selected by the algorithm, [a (1), ..., a (i - 1) , e] - call this new sequence a '. The algorithm continues - while its next options (for j> i) satisfy the condition a (j) = a (j - 1), we are healthy. There are two scenarios that break such a large strip (let them say that the strip is divided into index k + 1):

1) The algorithm selects some edge e ', which is not in T, and the weight (e') <weight (a (k + 1)). Currently "sequence:

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

But if it was possible to add e 'to this list, it would be possible to add it to [a (1), ..., a (k-1), a (k)]. But Kruskal's algorithm did not do this when searching for MST for G. This leads to a contradiction.

2) The algorithm is politely selected:

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

but decided to omit the edge a (k + 1). But if e was not in the list, the algorithm would decide to add (k + 1). This means that in the graph (V, {a (1), ..., a (k)}), the edge a (k + 1) will connect the same components as the edge e. And this means that after considering along the edge of the algorithm a (k + 1) in the case of G and G ', the division into related components (determined by the set of selected edges) is the same. Therefore, after processing, the algorithm (k + 1) will act identically in both cases.

Answer 2

When an edge is added to the graph without adding a node, this edge creates a cycle in the minimal spanning tree of the graph; the length of the cycle can vary from 2 to n, where n = there are no nodes in the graph. T = minimum spanning tree G Now, to find the MST for the (added edge T +), we just need to remove one edge from this loop .. so remove this edge that has the maximum weight.

So T 'always comes from TU {e}.

And if you think that this does not prove that the new MST will be the set of edges TU {e}, then analyze the Kruskal algorithm for the new graph. those. if e has a minimum weight, it must be selected for MST in accordance with the Kruskal algorithm, and here, if it is minimal, it cannot be removed from the loop.