Section 4.5 The Minimum Spanning Tree Problem

A minimum spanning tree is a tree that includes the smallest subset of edges that connect all the edges in the original graph. Additionally, in order to determine the minimum spanning tree of a graph all the edges in the graph must be strictly greater than zero and of distinct lengths.

This section proposes three algorithms to solve the graph for its minimum spanning tree, all of which will return a correct MST. The first algorithm sketched out is Kruskal's Algorithm, which successively adds edges starting with the least costly and adding edges so long as they do not create a cycle with edges that have already been inserted.

The next algorithm outlined is Prim's Algorithm. This one is similar to Dijkstra's in that it starts at a specified node and add the shortest edge that leads out from the current node to a node not yet visited. This algorithm also can not create a cycle since that would involve adding an edge that leads from the current node to an already-explored node.

The last algorithm discussed in this section is the Reverse-Delete Algorithm. As its name suggests, this algorithm works by deleting edges in the reverse order that they were added in the previous algorithms: from most expensive to least. It will not delete and edge that should otherwise be deleted according to the cost ordering if that edge will create a disconnected graph and this algorithm will terminate when the only remaining edges would disconnect the graph if deleted.

Additionally, the cut and cycle properties are treated by this section. The cut property says that S is any subset of nodes and e is the minimum cost edge with exactly one endpoint in S. Then the MST must contain e. The cycle property on the other hand says that C is any cycle and f is the max cost edge in C. Then the MST can not contain f.