Lecture 11 - Notes
February 15, 2016
Minimum Weight Spanning Trees
definition: A minimum weight spanning tree (MST) connects a graph using the lowest possible sum of edge weights.
Greedy Algorithms
We make two assumptions,
- The graph is connected
- Edge weights are distinct (no two edges of the same weight)
The consequence is that the minimum weight spanning tree exists and is unique.
Cut Property
definition: If we cut the graph along any number of edges the edge with the lowest weight will be in the MST.
Using the Cut Property
- Cut the graph on a set of edges that aren't in the MST yet.
- Add the smallest edge to the MST.
- Repeat until we have $V - 1$ edges in the tree.
Kruskal's Method
- Go through the edges from smallest to largest
- Add the edge as long as no cycle is created
Prim's Method
- Start with vertex 0 and grow the tree $T$
- Stop when we have $V-1$ edges