Assume existing two different spanning trees, say Ta and Tb. Let Ea={edges of Ta} Eb={edges of Tb} Let Eab={ edges that belongs to either of Ea and Eb but not both }. Eab is not empty, because Ta and Tb are different. Let e be the maximum weighted edge in Eab. Assume e belongs to Ea (Eb in same manner). We remove e from Ta, and Ta becomes two disjoint sub-trees Ta1 and Ta2. Let edge set Bridge={edges in Tb connecting Ta1 and Ta2} Bridge shouldn't be empty, otherwise Tb can't be a spanning tree. Meanwhile Bridge is contained by Eab, because there is no edges other than e connecting Ta1 and Ta2 in Ta. So e has a greater weight than any edge in Bridge and we can connect Ta1 and Ta2 with any edge in Bridge to get a spanning tree of smaller weight than Ta.
On 7/22/07, TheTravellingSalesman <[EMAIL PROTECTED]> wrote: > > > Your right but this part isn't necessarily evident. > > " There must exist a edge e' in Eb connecting Ta1 and Ta2 with a > smaller weight than e." > > ---> What if it isn't in Eb? And how do you know that the weight is > smaller, not larger of the connecting edge ? > > The idea is right but not necessarily evident........ > > ALso, for Yingjie Xu, Kruskals' algorithm is correct way to derive the > MST, since it takes a greedy approach all the way. However, we are > stating here that given a MST of a graph with unique edge > weights...prove that MST is unique...... > > I think that the approach for this has to be something like a proof by > contradiction. > > > On Jul 21, 3:38 am, "hongcheng zhu" <[EMAIL PROTECTED]> wrote: > > I have a simple proof. > > Assume existing two different spanning trees, say Ta and Tb. > > Let Ea={edges of Ta} Eb={edges of Tb} > > Let e be the maximum weighted edge that belongs to either of Ea and Eb > but > > not both. > > Assume e belongs to Ea. We remove e from Ta, and Ta becomes two disjoint > > sub-trees Ta1 and Ta2. > > There must exist a edge e' in Eb connecting Ta1 and Ta2 with a smaller > > weight than e. > > so we can connect Ta1 and Ta2 with e' to get a spanning tree of smaller > > weight than Ta. > > > > On 7/9/07, TheTravellingSalesman <[EMAIL PROTECTED]> wrote: > > > > > > > > > Prove that there is a unique minimum spanning tree on a connected > > > undirected graph when the edge weights > > > are unique. > > > > > > =============================================================================== > > > > > Makes intuitive sense but yet, I'm having a hard time trying to prove > > > it. I tried induction but I'm stuck...... any suggestions? > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---