CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
AturSams
AturSams

Reputation: 7962

Adding the lightest possible edges without affecting the graph's minimum spanning tree?

We have a graph G and wish to add edges between every vertex pair, that are as light as possible without affecting the minimum spanning tree. Given the minimum spanning tree and a pair of vertices, how would one compute the weight of the lightest edge that can be added between them without affecting the MST?

Thought adding an edge that is heavier than every other edge the two vertices have would work but it appears to be erroneous in trials I've conducted.

Upvotes: 0

Views: 361

Answers (2)

AturSams
AturSams

Reputation: 7962

Just to recapture and explain it in my own words (after accepting the answer):

To find the minimal weight for a newly added edge e between v and u (vertices in graph G), such that it does not improve (lighten) G's minimum spanning tree's weight, do the following:

  1. Find the path between v and u on the tree (there is only one such path).
  2. Find the heaviest edge(s) on that path.
  3. Make the newly added edge as heavy or heavier than that weight.

This will not affect the total weight of the tree.

Upvotes: 0

Nico Schertler
Nico Schertler

Reputation: 32627

The number of edges of a spanning tree is determined by the number of vertices. Hence, if you add an edge to the MST, you need to remove another in order to get a spanning tree. However, you cannot remove any edge. Obviously, removing an edge that is not on the path between the two vertices disconnects the graph. Therefore, you can only remove an edge on this path. If you want to find the minimum spanning tree, you would remove the heaviest edge, of course.

This new spanning tree is heavier than the original one iff the new edge's weight is greater than the heaviest edge weight on the old path. Therefore, the new edge must be heavier than this edge in order to keep the original MST.

Upvotes: 2

Related Questions