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