1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about min spanning tree property

  1. Apr 26, 2016 #1
    1. The problem statement, all variables and given/known data
    (a) If e is part of some MST of G, then it must be a lightest edge in some cutset of G.

    2. Relevant equations
    Cut property

    3. The attempt at a solution
    When the cutset has just one edge then yes it's true obviously. I am think I can do this by contradiction. Assuming e_i is part of some MST of G and e_i is not the lightest edge in any cutset. If this is true then, in every cutset, there exists an edge e_k such that e_k>e_i. I don't know how to go from here

    The cut property says For any cut C of the graph, if the weight of an edge in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

    It doesn't say anything about the larger edges in the cut
     
  2. jcsd
  3. Apr 26, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's a bit hard to give help on this without giving the whole thing away. Still, I'll try.

    Since the problem says 'for some cutset in G', it seems likely that there are some (possibly many, possibly even most) cutsets containing e in which e is not the lightest edge. So we might like to look for special cutsets (in which e does have the desired property), which is the same as looking for special partitions of the vertices. The other piece of info we have is that e is in a minimal spanning tree (MST), call that T.

    So, in the interests of finding a special partition of the vertices, using the info given, can you think of a partition of the vertices that is uniquely defined as a function of only G, T and e, without requiring any additional choices (which would necessarily be arbitrary)?
     
    Last edited: Apr 26, 2016
  4. Apr 27, 2016 #3

    Mark44

    Staff: Mentor

    OP has been banned for having multiple accounts, so the thread is now closed.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof about min spanning tree property
Loading...