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?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

ozoCommented:
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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
zxzwinAuthor Commented:
Great, thanks!
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.