Discrete Mathematics:

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.

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?

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.

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.

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.