Add new edge to graph and find new spanning tree

2
votes

Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G.

I) Check if T remains a MST or not. II) If not, give an efficient algorithm to find the minimum spanning tree of the graph G + e.

1
minimum-spanning-tree
What is your question? What have you tried? – Werner Henze
@WernerHenze Although the question obviously lacks an attempt at trying anything and is almost certainly homework, it is pretty clear what the question is - short of a question mark. – Timothy Shields
@WernerHenze, I had already seen this question on stackoverflow and got the same answers. My doubt is if other edges in the MST are still valid, but Timothy Shields explained below. Sorry for the incomplete explanation. – Rommel Dias

1 Answers

7
votes

Your current MST T contains n-1 edges. The addition to your graph of the new edge e = (u,v) with weight w creates exactly one cycle C in the graph T + e (T with edge e added). If the new edge weight (w) is less than the weight of the highest-weight edge in this cycle C, then you can create a lower weight MST by replacing that higher-weight edge with e. Otherwise, your current MST remains optimal.

The algorithm is basically this:

  1. Find the unique path P from u to v in T
  2. Find the edge e* in P that has maximum weight w*
  3. Is w < w*?
    • If so, then T' = T - e* + e is the MST for G + e,
      with weight(T') = weight(T) - w* + w
    • If not, then T' = T is the MST of G + e