retagged by
1,553 views
0 votes
0 votes
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'
retagged by

2 Answers

Best answer
3 votes
3 votes

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. 

selected by
1 votes
1 votes

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]

Related questions

3 votes
3 votes
1 answer
1
Pooja Palod asked Oct 15, 2015
2,991 views
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?
0 votes
0 votes
1 answer
2
gautamcse27 asked Sep 3, 2016
324 views
Given an adjacency-list representation of a directed graph, how long does it taketo compute the out-degree of every vertex? How long does it take to compute thein-degrees...
5 votes
5 votes
1 answer
3