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