cormen chapter 23 third edition.

Question

Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges in T. Show that T is still a minimum spanning tree for G. More formally, let T be a minimum spanning tree for G with edge weights given by weight function w. Choose one edge (x, y) ∈ T and a positive number k, and define the weight function w' by

w'(u, v) =  w(u, v), if (u, v) != (x, y),

w(u, v) − k, if (u, v) = (x, y).

Show that T is a minimum spanning tree for G with edge weights given by w'

Answer 1

A graph G:

Minimum spaning tree T: 

Now take any vertex (x,y)[take (c,f) $\epsilon$ T and search for that vertex if (u,v) = (x,y) then reduce weight by k [ assume k = 1].

Now reduce weight of C,F by 1 will make it 4 . which also a MST. 

Comments

In this question they mean that the reduction in weight of the edge is reflected in the graph also?

---

T $\subseteq$ G so yes change to G also happen.

---

thanku sir. So then obviously the new edge which is reduced will be one of the minimum edges of te graph and hence definitely be in MST. am i right?

---

Sir now if the edge whose weight is reduced is not present in MST. How will we modify the algorithm to compute MST?

Answer 2

In this graph if we decrease one of the edge weight, the MST will not change. Because MST already taken the minimum weights edges.

Now, weight of uv=1

weight of xy=4

So, k= -3 here.

(u,v)-(-3)=(x,y) [Proved]

Comments

Thanx a lot
 Plzz also answer the second part. What if the edge is not in mst

---

which edge?

---

The edge which we are reducing is not in mst. Then how will we compute the mst

---

Say, we are reducing the value of (u,x) and it is not in MST now, then e have to take xv in MST. Because MST cannot be disconnected,rt?