DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

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

1. Registered User
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. 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.

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

4. 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.

5. Registered User
Join Date
Jan 2005
Location
UK
Posts
604
Hi,
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

6. Registered User
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.
...

7. Senior Member
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 07:33 AM.

8. Registered User
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
•

 FAQ Latest Articles Java .NET XML Database Enterprise

×