4
$\begingroup$

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 $A\subset 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.

$\endgroup$
  • 1
    $\begingroup$ What kind of "why" are you looking for? (There are many proofs...) $\endgroup$ – Raphael Sep 19 '12 at 21:20
3
$\begingroup$

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 $A\setminus 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)\not\in 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.