We now can apply an exchange argument in the context of a second fundamental problem on graphs: the Minimum Spanning Tree Problem. The Problem. Our goal is to build a communication network with the least cost on top of a set of locations.We assume that the full graph G is connected, otherwise no solution is possible. The goal of our network design problem can be rephrased as that of finding the cheapest spanning tree of the graph ; for this reason it is called the Minimum Spanning Tree Problem. Designing Algorithms. Here are three of the greedy algorithms, each of which correctly finds a minimum spanning tree.
- Kruskal's Algorithm: Starts without any edges and successively inserts edges in order of increasing cost as long as it does not create a cycle. If it does create a cycle, we discard it and continue.
- Prim's Algorithm: Start with a node s and try to greedily grow a tree from s outward. We simply add the node that can be attached as cheaply as possible to the partial tree we already have.
- Reverse-Delete Algorithm: “backward” version of Kruskal's. Start with a full graph and delete edges in order of decresing cost if an edge does not disconnect the graph.
We shall also see reasons as to why so many different algorithms produce minimum-cost spanning trees. Analyzing the Algorithms. All these algorithms work repeatedly inserting or deleting edges from a partial solution. We assume all edge costs are distinct from one another. When is it safe to include an edge in the Minimum Spanning Tree? “Cut property”. Let S be a subset of nodes that is neither empty nor equal to V, and let an edge be the minimum-cost edge with one end in S and the other in V-S. then every minimum spanning tree contains that edge. Proof on Page 145. Both Kruskal's and Prim's Algorithms only include an edge when it is justified by the Cut property. Kruskal's and Prim's algorithm obth produce a minimum spanning tree of G. And the proofs for these claims are on page 146-147. When can we guarantee an edge is not in the minimum spanning tree? “Cycle Property”. Let C be any cycle in G, and let edge e the most expensive edge belonging to C. Then e does not belong to any minimum spanning tree of G. This statement is proven on page 147-148. Both properties assume all edges costs are distinct.
Reverse-Delete Algorithm also produces a minimuim spanning tree and it is justified by the Cycle property. This claim is proven on page 148-149. Any algorithm that builds a spanning tree by repeatedly including edges when justified by the Cut property and deleting edges when justified by the Cycle property will end up with a minimum spanning tree. This principle allows us to design more than three alforithms that are optimal in order to solve our problem.
Given an instance of the minimum spanning tree problem in which certain edges have the same cost, how can we conclude that the algorithms we have been discussing still provide optimal solutions???
The solution to this question is taing all the instance and pertubing all edge costs by different, extremely small numbers, so that they all become distinct. These pertubations serve as tie-breakers to resolve comparisons between edges that used to be equal. If we run any of our minimum spanning tree algorithms, using the pertubed costs for comparing edges, we will produce a minimum spanning tree T that is optimal for the original instance.
Implementing Prim's Algorithm. With the right choice of data structure, both Prim's and Kruskal's can be implemented in O(m logn) time. While this is difficult to achieve for Reverse-Delete, we are going to focus on Prim's in this section. Prim's algorithmis implementation is similar to Dijkstra's implementation. Using a priority queue, Prim's Algorithm can be implemented on a graph with n nodes and m edges to run in O(m) time, plus the time for n ExctractMin , and m ChangeKey operations. But is we use a heap-based PQ, we get an overall running time of O(m logn).
This section had a lot to digest but doable, thus its scale is an 7.5/10.
