
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:

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

Thanks Danny for suggestion. I will place my question to multiple areas.
Thanks

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 repost 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

Hi,
answer to 1) yes
answer to 2) not MSP, because there might be edge from T1nodes to T2nodes that are less heavy than intratree 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


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


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...ithmsweb.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; 10172006 at 07:33 AM.

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

Forum Rules

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