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