CSC301.01 2015F, Class 27: Minimum Spanning Trees, Continued
============================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Three approaches.
* Examples.
* Proofs of correctness.
* Running times.

Preliminaries
-------------

### Admin

* HW due.
* Next HW to be distributed this evening.
* Read 6.1 and 6.2.

### Questions

Three greedy approaches
-----------------------

* Repeatedly throw away the largest edge unless it disconnects the graph.
* Prim's: Throw away all the edges, pick a vertex, and repeatedly add 
  lowest weight edge that expands the tree of vertices reachable from 
  that vertex.
* Kruskal's Throw away all the edges, repeatedly add the lowest weight 
  edge that does not cause a cycle.

Examples
--------

* See white board.  All three algorithms performed the same.

Proofs of correctness
---------------------

* Try to break it!  We couldn't.
* Try to prove it correct.  Pick a strategy
    * Proof by contradiction.
    * Proof by strong or weak or structural induction.
    * Proof by construction.
    * When life gives you lemmas, make proof by lemmanade.
      (Proof via reduction to something previously solved.)
* Kruskal's: Proof via contradiction
    * Assume that Kruskal's algorithm produces something that is not an MST.
    * ...
    * Read it in the book.

Running times
-------------

### French's Algorithm

    Order the edges by weight: O(mlogm)
    For each edge, e, from largest to smallest:  m edges (m times ...)
      if removing edge e does not disconnect the graph, n+m for connectivity
        remove edge e

    O(m^2 + mn)

### Prim's Algorithm

    Add v to MST
    While there are vertices not in the MST,            O(n)
      find the closest vertex and add it to the MST     O(m) for obvious;
                                                        O(n) for clever

  O(nm) or O(n^2)

### Kruskal's Algorithm

    Order the edges by weight: O(mlogm)
    While the graph is disconnected
      add the smallest edge between two non-connected components