Skip to main content

Chapter 7 Spanning Trees

The left diagram in Figure 7.2 shows seventeen towns and the roads connecting them. The town with the circle has a power plant. Your job as a consultant to the power company is to decide which roads to install power lines on so that every town receives power and you install lines on as few roads as possible. You don't need a power line constructed down every road since you only need to ensure that there is a path for power to travel from the power station to each town.

Problem 7.1.

Using the diagram at the right of Figure 7.2, sketch a possible way to connect all the towns to the power station. Look for one that places power lines on the minimal number of roads.

Figure 7.2. Power Grid

Looking at our solutions, we probably believe they are correct. Still, what would we need to do in order to verify one of them? We would need to check that no collection of roads connecting all the towns to the power station has less roads than this solution. Because Problem 7.1 has only 17 towns, we might suspect that this would be easy. Surprisingly, Cayley studied such problems and proved that there can be up to \(n^{n-2}\) different solutions for \(n\) towns. If \(n=17\text{,}\) that is more than \(10^{18}\text{,}\) or a billion billion, cases to check! Would you be surprised that the language of graph theory might help?

Definition 7.3.

A tree is a connected graph with the property that no graph with the same vertices and a smaller number of edges is connected.

Definition 7.4.

A spanning tree of a graph \(G\) is a tree whose vertices are the same as the vertices of \(G\) and whose edges are among the edges of \(G\text{.}\)

Problem 7.5.

Is the power grid you created in the last problem a spanning tree?

Here are several equivalent definitions for trees. If you would like to create a proof of this theorem, work through the project section following this chapter.

Another real-world application for spanning trees might be to find the best possible collection of roads to plow when the city is snowed in. If we plow out a spanning tree then people may travel from any intersection (vertex) to any other intersection in the entire city by traversing only plowed streets (edges in the spanning tree). For a large city, computing the spanning tree by hand would be impractical. Here is an algorithm that a computer can implement.

Problem 7.9.

Prove that for any connected graph \(G\text{,}\) the Spanning Tree Algorithm always produces a spanning tree for \(G\text{.}\)

Applying the Spanning Tree Algorithm to the power grid problem illustrated in Figure 7.2, you could find many different spanning trees to build your power lines. Of course, in the real world, some would cost more to construct depending on both the distance between towns and the terrain between towns. Just as with the shortest path problems, this problem may be modeled mathematically using a weighted graph where the weights represent quantities like distances or costs.

Minimum Weight Spanning Tree Problem Given a weighted graph, find a spanning tree whose total weight is less than or equal to that of any other spanning tree.

In Figure 7.10, we have added weights to represent either distances (in miles) or road construction costs (in millions of dollars) between our 17 towns.

Figure 7.10. Weighted Power Grid
Problem 7.11.

Consider the weighted graph in Figure 7.10.

  1. Using this weighted graph, calculate the total weight of the spanning tree in your solution to Problem 7.1.

  2. Is your solution a minimum weight spanning tree?

  3. Find a spanning tree for the weighted graph in Figure 7.10 that has weight less than your solution to Problem 7.1.

  4. What is the least weighted spanning tree that you can find?

We can now ask if your solution to Part 4 of Problem 7.11 has minimal total weight among all possible spanning trees. How might we do this without looking at all possible spanning trees? The answer was discovered by Joseph Kruskal in 1956 and is simply the Spanning Tree Algorithm enhanced by the strategy used in the Cheapest Link Greedy Algorithm. Instead of choosing an arbitrary edge that doesn't complete a circuit, we choose the cheapest (least weight) one. Since Kruskal's Algorithm is also a greedy algorithm, it is practical and efficient to use. But unlike our other greedy algorithms, it always works!

Kruskal's important contribution was to show that his algorithm always produces a spanning tree of minimal possible total weight.

Problem 7.14.

Apply the Spanning Tree Algorithm to the graph in Figure 7.16 without looking at the weights. What is the total weight of the spanning tree you created?

Problem 7.15.

Apply Kruskal's Greedy Algorithm to the graph in Figure 7.16 to find a minimum weight spanning tree. What is the total weight of this spanning tree?

Figure 7.16. Connected Weighted Graph