Problem Detail: I was watching the video lecture from MIT on Prim’s algorithm for minimum spanning trees. Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum spanning tree of $G(V,E)$and let us call that $A$ such $Asubset B$, the edge with the least weight connecting $A$ to $V-A$ will always be in the minimum spanning tree ? The professor has done the swap step at point 59:07 seconds in the video.
Asked By : Geek
Answered By : A.Schulz
Charles Leiserson is presenting a proof to what is known as the blue rule in Tarjan’s “Data Structures and Network Analysis” book. The proof goes by contradiction, that is you assume that the edge $(u,v)$ is not in the MST $T$. Don’t be confused by the board, it has to be $(u,v)not in T$. Let $(a,b)$ the edge that we swap with $(u,v)$. Bot edges are cut edges between $A$ and $Asetminus V$. The tree $T’$ after the swap has weight $$w(T’)=w(T)+w((u,v))-w((a,b)).$$ As a consequence $w(T’)<w(T)$, which is a contradiction and therefor the assumption $(u,v)notin T$ was wrong. Notice that this proof uses the assumption that all edge weights are distinct, however it is easy to modify it for general edge weights.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4614 Ask a Question Download Related Notes/Documents
