Minimum Spanning Tree Question

Posted on 2008-11-17
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.
Question by:zxzwin
    LVL 84

    Accepted Solution

    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.

    Author Comment

    Great, thanks!

    Featured Post

    Do You Know the 4 Main Threat Actor Types?

    Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

    Join & Write a Comment

    Suggested Solutions

    Title # Comments Views Activity
    Baseline sigma 8 22
    sending sweets to asia!! 5 59
    new car buying (price bargaining) ideas.. 5 77
    Geomentry-Fundamental concepts 6 35
    Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
    Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
    Migrating to Microsoft Office 365 is becoming increasingly popular for organizations both large and small. If you have made the leap to Microsoft’s cloud platform, you know that you will need to create a corporate email signature for your Office 365…
    Hi everyone! This is Experts Exchange customer support.  This quick video will show you how to change your primary email address.  If you have any questions, then please Write a Comment below!

    733 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

    Need Help in Real-Time?

    Connect with top rated Experts

    22 Experts available now in Live!

    Get 1:1 Help Now