A-level Mathematics/OCR/D1/Node Graphs/Spanning Trees

In this module we will introduce the concept of the spanning tree, the minimum spanning tree, and some methods of finding minimum spanning trees.

Firstly, we must say what we mean by a tree. A tree is a graph where there is exactly one path between any pair of vertices. This means that a tree is connected, i.e. there exists at least one path between each pair of points.

A tree is the most efficient way of connecting a set of vertices, in the sense that if we have a tree then every edge is necessary, as if we remove any edge, then the graph is no longer connected. Also all trees on a graph with n vertices have exactly n - 1 edges.

If we have a connected graph G then another graph H is a spanning tree of G, if it is a tree with the same vertices as G, and all the edges of H are edges of G.

Finally, we will introduce the concept of a minimum spanning tree. For this to make sense, we must consider graphs called networks. A network is a graph where each edge has a weight. The weight can be the length of the edge, or the distance between the two points, or it could represent the difficulty of going between the points, or the cost. In any case, the weight is a number. It will usually be positive (or non-negative, with zero a possibility), but the maths is the same if we allow negative numbers. As it is each edge of the graph that will be assigned a distance, rather than the pairs of vertices themselves, no distance is assigned for pairs of vertices not joined by an edge.

Given a graph G with distances assigned to its edges, then a minimum spanning tree, H, is a spanning tree of G, where the sum of the weights of the edges are the lowest possible. There may be more than one minimum spanning tree. For a trivial example, any spanning tree of a graph G, with all weights 1, will be a minimum spanning tree, with the relevant sum equal to n-1, where n is the number of vertices of the original graph.

Kruskal's algorithm

Kruskal's algorithm is one way of finding a minimum spanning tree for a network G. We start with a graph H consisting of all the vertices of G, but with no edges. Then we follow the following instructions:

1. Consider the set E of edges in G, that will connect the end points when added to H
2. Find the member of E with the lowest weight. If there are more than one such member, pick any one.
3. Add this edge to H
4. If H is not connected, then go back to step 1. Otherwise, H is a minimum spanning tree of G.

Example

figure 1

Above is the diagram (figure 1) for a graph, for which a spanning tree will be constructed using Kruskal's algorithm. Each edge is given a weighting. The lines are dotted, as the edges of the spanning tree will be indicated with solid lines.

Below are figures 2 to 5, which indicate the stages of the construction of a spanning tree.

figure 2

figure 3

figure 4

figure 5

In figure 2, we add an edge of weight 2, as that is the edge of lowest weight. For figure 3 there are two options, both of weight 3, that could have been added. Note that the edge added is not connected to the first edge. This is allowed under this algorithm, but not Prim's algorithm, described below. In figure 4 the other edge of weight 3 is added. Finally, in figure 5 we add an edge of weight 6, out of two allowable. There are edges of lower weight, such as that of weight 4, but these all join edges we have already been connected. The final spanning tree is given below in figure 6, with the other edges in the original graph, and their weights, not given. The total weight is 2+3+3+6 = 14.

figure 6

Prim's algorithm

Prim's algorithm is an alternative way of finding a minimum spanning tree for a network G. Again, we start with a graph H, consisting of all the vertices of G, but with no edges. Then we follow the following instructions:

1. Pick any vertex v in the graph
2. Make it the only member of a set S
3. Consider the set E of edges joining one member of S to a vertex not in S.
4. Find the member of E with the lowest weight. If there are more than one such member, pick any one.
5. Add this edge to H, and the add the vertex not in S, to S.
6. If H is not connected, then go back to step 3. Otherwise, H is a minimum spanning tree of G.

Example

figure 7

Above is figure 7, which is the same as figure 1, the graph used for the example for Kruskal's algorithm. We will construct a different spanning tree, although as is guaranteed, the total weight will be the same. The first step is to choose a vertex to start with. This will be the top most vertex. Below are figures 8 to 11, the stages in the construction of a spanning tree.

figure 8

figure 9

figure 10

figure 11

At the start, only the top vertex is in S. The edges with lowest weight between S, and other vertices are those with weight 6, so in figure 8 one is chosen, thus adding the middle right vertex to S. In figure 9 the edge of weight 2 is added, adding the bottom right vertex to S. In figure 10, one of the edges of weight 3 is added, the other not having a vertex in S on either end. This edge is then added in figure 11. This is now allowed, as the middle left vertex was added to S in figure 10. The final spanning tree is given below in figure 12. The total weight is again 2+3+3+6=14, although the actual spanning tree is different from that for Krustal's algorithm.

figure 12

Matrix representation

An alternative way of finding minimum spanning trees is when the graph we are interested in is in matrix form. A matrix in this case is simply a table of numbers, the numbers corresponding to the weights of the edges. For example, below is table 1, the matrix form of the graph we have been using in our examples, along with figure 13, the familiar graphical representation:

table 1 1 2 3 4 5 1 8 6 6 9 2 8 3 3 4 3 6 3 5 2 4 6 3 5 7 5 9 4 2 7

figure 13

The vertices are given numbers 1 to 5, with 1 the top vertex, 2 and 3 the middle-left and middle-right vertices, and 4 and 5 the bottom-left and bottom-right. The row and column headings correspond to these numbers, and the other numbers are the weights of the appropriate edges. For example, the number 8 in row 1, column 2, is the weight, 8, of the edge between vertices 2 and 3. Note that there is symmetry in the matrix, in that, for example, row 2, column 1 is also 8. This is because the edge between 1 and 2, say, is also the edge between 2 and 1. Also, there is no edge between a vertex and itself, so row 1, column 1, row 2 column 2, etc., are all empty.

Using this form we can apply Prim's algorithm to find a minimum spanning tree. We will start with vertex 4, making that the only member of S. To denote this, we write it in bold, and will for other members of S later. You can use any method you want to indicate members of S, such as cicling. Below is table 2, with vertex 4 marked as a member of S.

table 2

	1	2	3	4	5
1		8	6	6	9
2	8		3	3	4
3	6	3		5	2
4	6	3	5		7
5	9	4	2	7

Now, we must pick the next edge. This will have one vertex in S, and one not in S. These correspond to the numbers in row 4 (the one in bold), where it doesn't cross column 4 (also in bold). This gives the numbers 6, 3, 5 and 7, the lowest of which is 3, which corresponds to row 4, colunn 2, so the edge between vertices 4 and 2. We thus add this to our tree, and 2 to S. Below is table 3, with both 2 and 4, the members of S, in bold.

table 3

	1	2	3	4	5
1		8	6	6	9
2	8		3	3	4
3	6	3		5	2
4	6	3	5		7
5	9	4	2	7

Now, the edges to select from correspond to numbers in rows 2 and 4 (those in bold), but not in columns 2 and 4. This gives the numbers 8, 3, 4, 6, 5 and 7. The lowest is 3, corresponding to an edge between vertices 2 and 3. Thus we add 3 to S, and this edge to our tree. Below is table 4, with 3 now in bold.

table 4

	1	2	3	4	5
1		8	6	6	9
2	8		3	3	4
3	6	3		5	2
4	6	3	5		7
5	9	4	2	7

Now, we have the numbers 8, 4, 6, 2, 5 and 7. The lowest is 2, which corresponds to the edge between vertices 3 to 5. We thus add this edge to our tree, and vertex 5 to S. In table 5, this vertex is added to S, and thus in bold.

table 5

	1	2	3	4	5
1		8	6	6	9
2	8		3	3	4
3	6	3		5	2
4	6	3	5		7
5	9	4	2	7

Here, the numbers are 8, 6, 6 and 9. There are thus two possible edges, between 1 and either 3 or 4. The previous edges were between 4 and 2, 2 and 3, and 3 and 5. Below are figure 14 and 15, images of the spanning trees formed by choosing one of the two edges. Figure 14 has the edge between vertices 1 and 3, and figure 15 that between 1 and 4.

figure 14

figure 15

Note that these are the spanning trees generated by Prim's algorithm, and Krustal's algorithm, respectively. Also note that when finding the lowest number, we only considered the case where the member of S is the row, and the non-member is the column. This leaves out the possibility that the member of S is the column, and the non-member is the row. However, as we have discussed, each edge is listed twice, and our way of considering elements includes each edge once. For example, if 1 is in S, and 2 not, then we include the edge between them as row 1, column 2, but not as row 2, column 1.