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.