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) is a subset of 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(x,y) - k if (u,v) = (x,y)
Show that T is a minimum spanning tree for G with edge weights given by w'.© BrainMass Inc. brainmass.com November 30, 2021, 12:57 am ad1c9bdddf
This solution shows how to solve the minimum spanning tree problem in an attached Word document.