Minimum Spanning Tree Question

Every minimum spanning tree of a graph has the property that the weight of every non-tree edge (u,v) is at least as large as the weight of all the edges on the u-v path of the tree T. Use Kruskals algorithm to show the converse: if a spanning tree T has the above property then it is a minimum spanning tree.

Suppose that T is a spanning tree that has this property and suppose that the edges of the graph are sorted in nondecreasing order of weight with ties broken in favor of the edges of T. Prove that Kruskals algorithm
outputs the tree T.
zxzwinAsked:
Who is Participating?
 
ozoConnect With a Mentor Commented:
Is this homework?
For the last claim, it should suffice to observe that Kruskal's algorithm will not add any edge that violates the property.
and if you believe that Kruskal's algorithm produces a Minimum Spanning Tree, then the first claim follows from the second.
0
 
zxzwinAuthor Commented:
Great, thanks!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.