Graphs connect nodes with edges, but graphics may have more edges than necessary for some applications. For example, suppose we have several locations we want to interconnect with communication cables. There are possible routes that the cables can be laid along, with different costs per route. These routes can be represented as edges in a graph in which the nodes are the locations to be conncted. Ultimately we just need to ensure that any two locations are connected via some route. Can we choose edges from the original graph in such a way that every pair of nodes is connected and, what's more, the total cost is minimized? Perhaps surprisingly, this problems and similar problems can be solved efficiently.
An undirected graph is a tree if there is exactly one simple path between any two pair of nodes. Equivalently, an undirected graph is a tree if it is connected—there is a path between any pair of nodes—and acyclic. In fact, any two of the following three facts ensures that an undirected graph is a tree, and implies the third fact:
A spanning tree of a graph (V, E) is a subgraph (V, E') in which E is a subset of E' and the subgraph is a tree. It has the same set of nodes but possibly fewer edges.
Finding a spanning tree is not difficult. We can start with the original graph and keep removing any edges that are part of cycles until there are no more cycles and a spanning tree is reached. Notice that if we remove an edge from a cycle, it cannot disconnect the graph. This is a subtractive algorithm.
Alternatively, we can do things additively: start with no edges and keep adding edges as long as they do not create cycles. Stop when there is only one connected component. At that point we will have an acyclic graph with |E| = |V|−1, which is a spanning tree.
Assume the graph edges come with weights. We want to find a spanning tree that minimizes the total weight of all its edges. There may be more than one equally good minimum spanning tree, in which case we are satisfied with any of them.
An additive algorithm. Idea: start with an empty set of edges and add the minimum-weight edge in the graph that does not create a cycle to the set. Repeat until a spanning tree is achieved.
An additive algorithm. Idea: start with an empty set of edges and add the minimum-weight edge in the graph that does not create a cycle and that is connected to the existing set of connected nodes until a spanning tree is achieved. This is a bit reminiscent of Dijkstra's SSP algorithm.
A subtractive algorithm. Idea: start with all edges and remove the maximum-weight edge from the graph that does not disconnect the graph until a spanning tree is achieved.
(These notes still under construction.)