# Minimum Spanning Tree

Not what you're looking for? Search our solutions OR ask your own Custom 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) 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 ad1c9bdddfhttps://brainmass.com/computer-science/trees/minimum-spanning-tree-73417

#### Solution Summary

This solution shows how to solve the minimum spanning tree problem in an attached Word document.

$2.49