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