Printable View
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.
There are two algorithms which is Kruskal and Prim's algorithm.
can u plz explain ur answer??
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
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.