OT: Need help to find more infor for MST (minimum spanning tree) and Kruskal runtime


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 8 of 8

Thread: OT: Need help to find more infor for MST (minimum spanning tree) and Kruskal runtime

  1. #1
    Join Date
    Sep 2006
    Posts
    17

    OT: Need help to find more infor for MST (minimum spanning tree) and Kruskal runtime

    Hi,
    Can anyone please guide me where can I find the specific information to prove the follwing. (I tried enough but not found the specific info for this!)

    (1) I have a weighted graph G. Suppose that we divide the vertices of G into two disjoint subsets S1 and S2. We then find an MST T1 for S1 and an MST T2 for S2. Finally, we find a minimum weight edge x connecting T1 and T2. We then let T be the graph obtained by combining T1, T2, and x.
    1. Is T always a spanning tree?
    2. If T is a spanning tree, is it always an MST?

    (2) Let x be an edge in a connected, weighted graph G. Prove, If the weight of x is less than the weight of every other edge, x is in every minimum spanning tree of G.
    thanks :confused:

  2. #2
    Join Date
    Nov 2003
    Posts
    4,118
    It's a bit off topic here (you could as well have posted it on any other programming forum, frankly) but if members here are kind enough to give you a few pointers, so be it.
    Danny Kalev

  3. #3
    Join Date
    Sep 2006
    Posts
    17
    Thanks Danny for suggestion. I will place my question to multiple areas.
    Thanks

  4. #4
    Join Date
    Nov 2003
    Posts
    4,118
    That's not what I meant, actually. Crossposting is rarely welcome on forums, so if you'ev decided to post here, my advice is to wait a few days for an answer, and only then re-post it elsewhere. Note that crossposting is automatically detected by vBulletin so it could cause your posts to be deleted or marked as spam.
    Danny Kalev

  5. #5
    Join Date
    Jan 2005
    Location
    UK
    Posts
    604
    Hi,
    answer to 1) yes
    answer to 2) not MSP, because there might be edge from T1-nodes to T2-nodes that are less heavy than intra-tree edges.
    answer to 3) I suggest you start the proof by supposing the stated is false which means there is a MST in which x is not an edge and proof that you can reduce the weight of your tree by including x. shouldn't be too difficult.
    and try to search for "minimum span tree" on say
    www.metacrawler.com

    http://www.csse.monash.edu.au/~lloyd...ph/Undirected/
    http://www.people.vcu.edu/~gasmerom/MAT131/mst.html
    and thousands more...

    Cheers,
    D
    DKyb
    -------------------------------
    Life is a short warm moment -
    Death is the long cold rest.
    Pink Floyd
    -------------------------------

  6. #6
    Join Date
    Jan 2005
    Location
    UK
    Posts
    604
    Sorry my previous post was probably not absolutely correct in regards to answer1:
    If we talk about a binary tree here then obviously you cannot chose any old x to connect your trees. you can only choose a leave in one tree and you have to find an edge to the root of the other or to any inner node that only has one child.
    ...
    DKyb
    -------------------------------
    Life is a short warm moment -
    Death is the long cold rest.
    Pink Floyd
    -------------------------------

  7. #7
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    Take a look at explanations/proofs of Baruvka's Algorithm as well as Kruskal's at, for example:

    http://cgm.cs.mcgill.ca/~godfried/te...ithms-web.html

    The proofs you are looking for (all of your answers are "Yes") can also be found in Chapter 23 of Cormen, et al.'s "Introduction to Algorithms" and section 7.3 (page 361) of Goodrich & Tomassa's "Algorithm Design".
    Last edited by nspils; 10-17-2006 at 08:33 AM.

  8. #8
    Join Date
    Sep 2006
    Posts
    17

    Thanks to all for help!

    Hi all;
    Whoever replied to me for my questions, I appreciate your time and valuable input.

    Thanks again.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center