Proof of the correctness of Kruskal's MST algorithm

[Amrinder Arora]

Can someone write that up the proof of the Kruskal's algorithm that we did during Sunday session?  I wrote on the board, but forgot to press the print button on the chalkboard in Gelman 402.

[Maya Larson]

I happen to be studying right now & and have those notes right in front of me so I will do it.   Maya

On Jun 26, 2012 1:32 PM, "Amrinder Arora" <amrinde...@gmail.com> wrote:

Can someone write that up the proof of the Kruskal's algorithm that we did during Sunday session?  I wrote on the board, but forgot to press the print button on the chalkboard in Gelman 402.

--
You received this message because you are subscribed to the Google Groups "CS 6212 Summer 2012" group.
To post to this group, send email to cs-6212-s...@googlegroups.com.
To unsubscribe from this group, send email to cs-6212-summer-...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg/cs-6212-summer-2012/-/k6h3KNkjd9wJ.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Maya Larson]

The proof is posted on Blackboard now.  Attached and below too in case that might be helpful for people.
_____________________________________________________


Proof of Kruskal’s Algorithm:

Hypothesis
Tk, Tree produced by Kruskal's algorithm, is not optimal.

Proof
Then, there exists, a T’ such that cost(T’) < cost(Tk), where T' is a
spanning tree and Tk is Kruskal’s tree.

For all we know, there may be many such trees with cost lower than
Kruskal.  By choice, we use T’ that has THE LOWEST cost, and among all
lowest cost trees, we select the one that has the MOST edges in common
with Tk.

[Note: The choice is very important in proofs by contradiction to help

contradict the hypothesis.  The choice axioms make your hypothesis
more refined, easier to prove.  In this case, it brings the proof down
to one edge.]

Since cost(T') < cost (Tk), this means that there exists an edge e such that
e is not an element in T’ and e is an element in Tk.

Compare e’ with ek, where ek and e' are edges between same two
components.  Since Tk is a spanning tree, these two components must be
connected, and therefore edge ek must exist.
Remove e’ from T’ and add ek instead.
So now we have a third Tree T’’ such that T’’ = T’ – e’ + ek.
Because e’ is not in Kruskal’s tree Tk, and Kruskal considers edges in
order of weight, that means ek must have been considered before e',
therefore cost(ek) <=  cost(e’)

So cost(T’) ≥ cost(T’’) so there exists another Tree T’’ such that T’’
is also optimal.

Since all edges other than ek are the same in T’ and T’’, then we have
one of two possibilities:

Either cost(ek) < cost(e’) then, cost(T'') < cost(T’).
Or, the costs of T' and T'' are the same, but now T'' has one more
edge in common with Tk than T'

In either case, we have a contradiction.

Therefore Tk is optimal.




______________________________________________________

On Tue, Jun 26, 2012 at 1:32 PM, Amrinder Arora <amrinde...@gmail.com> wrote:

Can someone write that up the proof of the Kruskal's algorithm that we did during Sunday session?  I wrote on the board, but forgot to press the print button on the chalkboard in Gelman 402.

--

[Bryan Batty]

Thanks, Maya!