====== Chapter 4.5: Minimum Spanning Trees ======
Suppose we have a set of locations //V={v_1, v_2,..., v_n}// and we want to build a communication network on top of them. There should be a path between every pair of nodes, but other than this, we want to build as cheaply as possible. If //T// is the minimum cost solution to this problem, then //(V,T)// is a tree. There are several greedy algorithms that provide an optimal solution to this problem.
  * Start without any edges and build a spanning tree that successively inserts edges in order of increasing cost. As we move through the edges in this order, we only insert an edge if it does not create a cycle in the graph. If the edge does create a cycle, then we discard it and continue on. This is called **Kruskal's Algorithm**.
  * Start with a root node //s// and greedily grow a tree from //s// outward. At each step, we add the node that can be attached as cheaply as possible to the partial tree we already have. This is called **Prim's Algorithm**.
  * Start with the full graph //(V,E)// and begin deleting edges in order of decreasing cost. We delete each edge so long as it does not disconnect the graph we currently have. This is called the **Reverse-Delete Algorithm**.

All of these algorithms produce a minimum spanning tree of //G//.

Assume that all edge costs are distinct. Let //S// be any subset of nodes that is neither empty nor equal to all of //V//, and let edge //e=(v,w)// be the minimum-cost edge with one end in //S// and the other in //V-S//. Then every minimum spanning tree contains edge //e//.

Assume that all edge costs are distinct. Let //C// be any cycle in //G//, and let edge //e=(v,w)// be the most expensive edge belonging to //C//. Then //e// does not belong to any minimum spanning tree of //G//.

Both Prim's and Kruskal's Algorithms run in O(mlogn) time. For Prim's, this is because it can be implemented with a priority queue, similarly to Dijkstra's Algorithm.

I'd rate this section a 7. It wasn't too difficult to read but it had a lot of information in it. I was able to follow the lectures better.