-
March 28th, 2009, 03:57 AM
#1
simple MST problem
can someone plz give me the solution to this problem--
Show that if an edge(u,v)is contained in some MST, then it is a light edge crossing some cut of the graph.
i have very little idea graphs...therfore a detailed soln will be welcome...
plz help as soon as possible.
-
March 28th, 2009, 05:43 AM
#2
Re: simple MST problem
There are two algorithms which is Kruskal and Prim's algorithm.
Thanks for your help.
-
March 28th, 2009, 06:39 AM
#3
Re: simple MST problem
can u plz explain ur answer??
-
March 28th, 2009, 03:34 PM
#4
Re: simple MST problem
Hi,
If this is a homework assignment (and it sounds like one), please take a look at this.
Now, after you show some genuine effort, it would help writing your question in a little more detail, especially if you use some special definitions,
e.g. "light edge" (?)
P.S: I believe the solution requires some sort of formal proof, therefore Peter's answer probably doesn't mean anything - Kruskal's and Prim's are just 2 algorithms for finding a MST in a graph.
Regards,
Zachm
Last edited by Zachm; March 28th, 2009 at 03:36 PM.
-
March 29th, 2009, 02:19 AM
#5
Re: simple MST problem
A cut (S, V − S) of an undirected graph G = (V,E) is a partition of V .
An edge (u, v) crosses the cut iff one of ts endpoints is in S and the other is in V −S.
An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.
P.S.-it is a homework assignment...
but the thing is that we hvnt been taught graphs as of yet in our Data Structure class. nonetheless, we are expected to submit it by the 4th of april. i tried studying it by myself, but couldnt understand most of the things. however, i managed to understand the above defintions.
i understand your policies regarding hw assignments, but i need your expert help urgently.
Tags for this Thread
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
|
Click Here to Expand Forum to Full Width
|