Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of

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


if (u, v) # (x, y). w(u, v) w(x, y) - k if (u, v) = (x, y). w'(u, v) =

Show that T is a minimum spanning tree for G with edge weights given by w′.
Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: