[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Minimum Spanning Tree Question

Posted on 2008-11-17
2
Medium Priority
?
584 Views
Last Modified: 2012-05-05
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.
0
Comment
Question by:zxzwin
2 Comments
 
LVL 85

Accepted Solution

by:
ozo earned 1000 total points
ID: 22983401
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
 

Author Comment

by:zxzwin
ID: 23002392
Great, thanks!
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Aerodynamic noise is the cause of the majority of the noise produced by helicopters. The inordinate amount of noise helicopters produce is a major problem in the both a military and civilian setting. To remedy this problem the use of an aerogel coat…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Suggested Courses
Course of the Month18 days, 22 hours left to enroll

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question