## 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.

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.

###### Theorem 7.6.

*Equivalent Tree Definitions.* For a connected graph \(G\text{,}\) the following are equivalent.

\(G\) is a tree.

Every edge of \(G\) is a cut edge (Definition 5.29).

\(G\) has no circuit.

The number of edges in \(G\) is one less than the number of vertices.

###### Problem 7.7.

Use Theorem 7.6 to give three different ways to show why your answer to Problem 7.1 is correct.

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.

###### Theorem 7.8.

*Spanning Tree Algorithm.* To construct a spanning tree for a connected graph \(G\text{,}\) make another copy of the vertices of \(G\text{.}\) Then

add edges from \(G\) between these vertices one at a time making sure to never close a circuit, and

stop when no additional edge from \(G\) can be added without closing a circuit.

###### 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.

###### Problem 7.11.

Consider the weighted graph in Figure 7.10.

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

Is your solution a minimum weight spanning tree?

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

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*!

###### Theorem 7.12.

*Kruskal's Greedy Algorithm.* To construct a minimum weight spanning tree for a connected weighted graph \(G\text{,}\) make another copy of the vertices of G. Then

add edges from G between these vertices one at a time, each time choosing from among the edges that do not close a circuit one of minimal weight, and

stop when no additional edge from \(G\) can be added without closing a circuit.

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

###### Theorem 7.13.

*Kruskal's Theorem.* Kruskal's Greedy Algorithm always produces a minimum weight spanning tree \(T\) from a connected weighted graph \(G\text{.}\)

A proof is outlined in the project following this chapter.

###### 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?