thank u for ur answer. however can u still tel me the page no of CLRS in which the soln is given? On Mar 29, 10:22 pm, Miroslav Balaz <gpsla...@googlemail.com> wrote: > do you have CLRS? i mean introduction to algorithms book, it is there > exactly done... > > but the proof is easy, by contradiction. You assume you have MST and , if > you remove one edge, then you have two components, and there is one cut > between them... now every edge in that cut must not have smaller weight, > than removed edge, because if not , you would get more minimum spanning > tree. > > thats all. > > Indeed if all adges have different weight, then iff holds. > > 2009/3/29 saha.dipan...@gmail.com <saha.dipan...@gmail.com> > > > > > A cut (S, V − S) of an undirected > > graph G = (V,E) is a partition of V . > > > An edge (u, v) ∈ E crosses the cut iff one of > > its 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.
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
