Cheap and Secure Web Hosting Provider : See Now

[Answers] Unclear about proof for unique MST given graph G with distinct weights

, , No Comments
Problem Detail: 

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf enter image description here

I have some trouble understanding the proof above.

I understand that we assuming two MSTs, T and T', and an edge e that is the cheapest edge of G that located in T. Then the weight of this edge is larger than any weight on T', given that T' contains (x,y), by definition of MST.

My question is why do we assume that T' passes through (x,y)? Wouldn't it natural to assume that T' is completely disjoint from T?

Asked By : Beached Whale

Answered By : Yuval Filmus

The edge $e$ is not necessarily the cheapest edge of $G$ that is in $T$. Rather, it is the cheapest edge in the symmetric difference $T \triangle T'$. It could belong to either $T$ or $T'$ (but not both!), but since both cases are the same, we assume that it belongs to $T$ without loss of generality.

We don't need to separately consider the case that $T$ is disjoint from $T'$ and the case that they share some edges. All we need to know is that they are different and so their symmetric difference is not empty.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35401

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback