I decided this semester to take an algorithms course, in an attempt to finally learn some discrete math. As of late, we have been talking about graph algorithms. The problem is that, having never thought much about graphs, I don’t have a great deal of intuition for them. So I want to devote a post to try to help myself understand this material better.

The problem we are currently concerned with is the following. Let {G = (V, E)} be an undirected graph, such that each edge {e \in E} has a “weight” or “cost” {w(e) \in \mathbb{R}} associated with it. The problem is to find a minimal spanning tree. That is, a subtree {T \subset G} containing all the vertices and such that {\sum_{e \in T} w(e)} is minimal. The naive approach of listing every possible tree and calculating the weights for each of them is horribly inefficient here, as the number of trees on a complete graph of size {n} grows super-exponentially.

1. Trees

To start with, I will recall the definition of a tree. All graphs will be undirected.

Definition 1 A tree is a connected graph containing no cycles.

Intuitively, one has the standard picture of a node branching out into several nodes, each of which branch into several other nodes, and so on. In fact, with the above definition one can show in fact the precise analog of the preceding statement: the “geometric realization” of a tree (when considered as a simplicial complex) is contractible. The above definition is precise, and furthermore is equivalent to the following. An easy consequence of the definition, that we will use, is that a connected subgraph of a tree is tree.

Given a graph {G}, we are interested in the following problem: Is there a subgraph {T \subset G} which is a tree and which contains every vertex of {G}? Such a subgraph is called a spanning tree. Physically, there are reasonable instances where one might wish to find one, such as in building a pipeline system. The claim is that a spanning tree always exists. To see this, we shall use the following characterization of trees:

Proposition 2 A graph is a tree if and only if it is connected and removing any edge would make it disconnected.

So trees are precisely the minimal connected graphs.

Proof: Let {G=(V,E)} be a tree, and let {e} be an edge in {G} from {v_1} to {v_2}. The claim is that the graph {G-e}, which is just the pair {(V, E-\left\{e\right\})}, is disconnected. For if there were a path {\rho} between {v_1} and {v_2} that did not pass through {e}, then we could consider {\rho} and the reversal of {e} to get a cycle. This proves one direction.

For the other, suppose {G} is a minimal connected graph. Then if {G} had a cycle {v_1 v_2 \dots v_n}, where {v_1 = v_n}, then we can remove the edge {v_1 v_2} without destroying any connectedness—indeed, all the {v_i} are still connected to each other by the rest of the cycle. From this we can see that spanning trees exist:

Proposition 3 Let {G} be a connected graph. Then {G} has a spanning tree.

Proof: Indeed, we can take {G}, and choose a subgraph of {G} that is minimal with respect to being connected (i.e. such that removing any edge would disconnect it). We have seen that this is a tree, and it is clearly spanning.

Example 1 In fact, we now see an algorithm for determining a spanning tree in a graph. Namely, we construct a sequence of graphs {G^{(0)}=G, G^{(1)}, G^{(2)}, \dots}. The algorithm starts with {G^{(0)}=G}. Given {G^{(n)}}, we try removing each of the edges, one at a time, and test whether the resulting smaller graph is connected. If none of these {G^{(n)}-\left\{e\right\}} graphs (for {e \in G^{(n)}} an edge) is connected, then we stop at {G^{(n)}}, which we have seen is a tree. If we get something that is connected, we let {G^{(n+1)}} to be {G^{(n)}} with this edge removed. It is obvious that this algorithm is correct from the above discussions. But it is not necessarily efficient. To determine whether a graph is connected, we could for instance perform a breadth-first search, whose time is linear in the size of the graph. This graph has at most {|E|} steps, each of which may involve {|E|} breadth-first searches, each of which takes {O(|E|)} time. So the algorithm runs in cubic time.

We have the following additional simple characterization of trees.

Proposition 4 A connected graph {G = (V, E)} is a tree if and only if\displaystyle |E| = |V|-1.

Proof: The idea is that adding an edge to a graph can connect two connected components. So adding an edge can cut down the number of components by at most one. Thus if {G=(V,E)} has one less edge than vertex, if we remove one of its edges, then it will be disconnected as there will be too few edges to make the graph connected. So if we have {|E|=|V|-1}, then {G } is a minimal connected graph.

Conversely, suppose {G=(V,E)} is a tree. Then if we remove an edge from {E}, we find that the new graph {G- \left\{e\right\}} is disconnected—so it is a disjoint union of trees. It must be the union of two trees or the edge {e} could not join them into one connected graph {G}. If we induct on the size of the tree, we can compute the vertex and edge counts of {G} by those of the two subcomponents. From this the result becomes clear.

2. Minimum spanning trees

There is a more serious problem. In practice, the graphs for which we want a spanning tree may be weighted, with each edge assigned to a cost, and we will want a spanning tree that minimizes the cost.

Definition 5 A weight on a graph {G=(V,E)} is a function {w: E \rightarrow \mathbb{R}}. A spanning tree {T \subset G} is said to be minimal if the sum\displaystyle \sum_{e \in T} w(e)

is minimized, over spanning trees.

If we take the identity weight {w \equiv 1} on our graph, then any spanning tree is a minimum spanning tree. Indeed, this is immediate because any two spanning trees have the same cardinality (namely, {|V|-1}).

We would now like an algorithm to obtain a minimum spanning tree. The algorithms we shall use will be greedy; that is, they shall add edges starting with the smallest weight (possibly subject to some condition). To approach the idea of building a minimum spanning tree from nothing, we shall need some induction. Namely, we will start with a subgraph that is known to be contained in a minimal spanning tree, and we will want to grow that to a bigger subgraph that is still contained in a minimal spanning tree. We will keep doing this until all the vertices of {G} have been incorporated, at which point we will necessarily have a minimal spanning tree.

To make things convenient, we fix some notation. Let {G=(V,E)} be a graph.

Definition 6 A subgraph {H \subset G} is said to cut {G} into sets {S, T} if {G = S \cup T} (disjoint union) and no edge of {H} is between {S } and {T}.

In other words, if we add all the vertices of {G} to {H} to get a new graph {H'}, then {S} and {T} are just unions of disjoint connected components of {H'}.

Proposition 7 (The cut property) Let {G=(V,E)} be a graph, and let {H \subset G} be a subgraph of {G} which is contained in a minimal spanning tree. Suppose {H} cuts {G} into a disjoint union {S \cup T}. Then if {e \in E} is an edge from {S} to {T} (in {G}) of minimal weight, then {H \cup \left\{e\right\}} is contained in a minimal spanning tree.

Of course, there is a guarantee that {e \notin H}.

Proof: Let us suppose that {H} is contained in the minimum spanning tree {T}. Then {T} contains all the vertices of {G}, and it is connected, so there is an edge {e' \in T} from {S } to {T}. This edge does not belong to {H} by hypothesis.

The claim is that {T - \left\{e'\right\} \cup \left\{e\right\}} is still a minimum spanning tree, which clearly contains {H \cup \left\{e\right\}}. To see this, we note that {T \cup \left\{e\right\}} necessarily has a cycle. This cycle has an edge {e} going from {S} to {T}, so it must contain another edge {e'} going from {T} to {S}.

Now {T'=T - \left\{e'\right\} \cup \left\{e\right\}} is connected (since removing on edge in a cycle does not change connectedness), and it is thus a tree because

\displaystyle |T'| = |T - \left\{e'\right\} \cup \left\{e\right\}| = |T| = |V|-1.

The claim is that it is a minimal spanning tree. But the weight of {T'} can be at most the weight of {T}, since {e'} has at least the same weight as {e}. It follows that {T} is a minimum spanning tree as well.

3. Kruskal’s algorithm

Based on the above “cut property,” we can define an efficient way of finding minimum spanning trees. As described, we will grow them, step by step. Let us now describe an algorithm due to Kruskal.

We will start the tree with a graph {T^{(0)}} that is not a tree—namely, the empty graph on the vertices of {G}. Successively we will add edges to this graph to join connected components, making a sequence of graphs {T^{(0)}, T^{(1)}, T^{(2)}, \dots}. To do this, we will need an auxiliary data structure {\mathbf{Set}}.

In detail, here is the algorithm. We start by placing each of the vertices of {G} into its own set. So we have a collection {C_0} of sets. At each stage {i}, we will have a collection {C_i} of sets that contains the connected components of the graph {T^{(i)}}; since {T^{(0)}} is the empty graph, it is clear that {C_0} is the set of connected components of {T^{(0)}}.

We now construct the {T^{(i)}} inductively. We start by generating a sorted list of the edges {E}, sorted by weight in ascending order. We list the edges {e_1, \dots, e_N}. We now add edge {e_1} to the graph {T^{(0)}}, making a new graph {T^{(1)}}.

We then consider the components in {C_0} that contain the vertices of {e_1} and join them to make the new collection {C_1} of sets; clearly {C_1} is the collection of connected components of {T^{(1)}}. To decide whether to add {e_2} to the graph {T^{(1)}}, we look through the collection {C_1} and determine whether {e_2} joins two connected components of {T^{(1)}}. If it does, we add {e_2}; if not, we don’t.

Inductively, the construction is as follows. At stage {i}, let us suppose inductively that {T^{(i-1)}} has been constructed, and that the vertices of {G} are partitioned into a collection of sets {C_{i-1}} that represents the connected components of {T^{(i-1)}}. Then we split into two steps:

  1. If {e_i} connects two connected components of {T^{(i-1)} } (as we can check by a look at {C_{i-1}}), then we let {T^{(i)} = T^{(i-1)} \cup \left\{e_i\right\}}, and we merge the two connected components in {C_{i-1}} corresponding to the endpoints of {e_i}.
  2. If the endpoints of {e_i} lie in the same connected component of the partial graph {T^{(i-1)},} then we just take {T^{(i)}= T^{(i-1)}}.

The algorithm stops when {|V|-1} edges have been added.

Theorem 8 Given a connected weighted graph {G = (V,E)}, Kruskal’s algorithm always produces a minimal spanning tree.

Proof: This will be a straightforward argument from the cut property. Let us inductively suppose that {T^{(i-1)}} is contained in a minimal spanning tree; then we shall show that {T^{(i)}} is too.

As above, there were two cases to the above algorithm: in the second, we just had {T^{(i)}= T^{(i-1)}}, and there was nothing to prove. We need to show that {T^{(i)}} is contained in a minimal spanning tree in the first case. To see this, let us apply the cut property to {T^{(i-1)}}. By assumption, there are two connected components of {T^{(i-1)}} that the edge {e_i} joins; thus we can partition {V = V_1 \cup V_2} such that no edge of {T^{(i-1)}} connects {V_1, V_2} and such that {e_i} does connect {V_1, V_2}.

We now need to show that, among the edges connecting {V_1, V_2}, {e_i} is the one with minimal weight. But if {e_i} did not have minimal weight among edges connecting {V_1, V_2}, there would have been an edge {e_j, j<i} that also connected vertices in {V_1, V_2} (which cannot be in {T^{(i-1)}}). However, {e_j} would then have been added to the graph at stage {j} for joining two connected components of {T^{(j)} \subset T^{(i-1)}}, which is a contradiction.