6.7: Spanning Trees

A company requires reliable internet and phone connectivity between their five offices (named A, B, C, D, and E for simplicity) in New York, so they decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph.

In this case, we don’t need to find a circuit, or even a specific path; all we need to do is make sure we can make a call from any office to any other. In other words, we need to be sure there is a path from any vertex to any other vertex.

Spanning Tree

A spanning tree is a connected graph using all vertices in which there are no circuits.

In other words, there is a path from any vertex to any other vertex, but no circuits.

Some examples of spanning trees are shown below. Notice there are no circuits in the trees, and it is fine to have vertices with degree higher than two.

Usually we have a starting graph to work from, like in the phone example above. In this case, we form our spanning tree by finding a subgraph – a new graph formed using all the vertices but only some of the edges from the original graph. No edges will be created where they didn’t already exist.

Of course, any random spanning tree isn’t really what we want. We want the minimum cost spanning tree (MCST).

Minimum Cost Spanning Tree (MCST)

The minimum cost spanning tree is the spanning tree with the smallest total edge weight.

A nearest neighbor style approach doesn’t make as much sense here since we don’t need a circuit, so instead we will take an approach similar to sorted edges.

Kruskal’s Algorithm

1. Select the cheapest unused edge in the graph.
2. Repeat step 1, adding the cheapest unused edge, unless:
   1. adding the edge would create a circuit
3. Repeat until a spanning tree is formed

Example 22

Using our phone line graph from above, begin adding edges:

\(\begin{array}{lll}\mathrm{AB} & \$ 4 & \mathrm{OK} \\ \mathrm{AE} & \$ 5 & \mathrm{OK}
\\ \text {BE } & \$\text {6} & \text {reject-closes circuit ABEA} \\ \text {DC} & \$ 7 & \text {OK} \\ \text {AC} & \$ 8 & \text {OK}\end{array}\)

At this point we stop – every vertex is now connected, so we have formed a spanning tree with cost $24 thousand a year.

Remarkably, Kruskal’s algorithm is both optimal and efficient; we are guaranteed to always produce the optimal MCST.

Example 23

The power company needs to lay updated distribution lines connecting the ten Oregon cities below to the power grid. How can they minimize the amount of new line to lay?

\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline & & & & & & & & & & \\
& \text { Ashland } & \text { Astoria } & \text { Bend } & \text { Corvallis } & \text { Crater Lake } & \text { Eugene } & \text { Newport } & \text { Portland } & \text { Salem } & \text { Seaside } \\
\hline \text { Ashland } & \_ & 374 & 200 & 223 & 108 & 178 & 252 & 285 & 240 & 356 \\
\hline \text { Astoria } & 374 & \_ & 255 & 166 & 433 & 199 & 135 & 95 & 136 & 17 \\
\hline \text { Bend } & 200 & 255 & \_ & 128 & 277 & 128 & 180 & 160 & 131 & 247 \\
\hline \text { Corvallis } & 223 & 166 & 128 & \_ & 430 & 47 & 52 & 84 & 40 & 155 \\
\hline \text { Crater Lake } & 108 & 433 & 277 & 430 & \_ & 453 & 478 & 344 & 389 & 423 \\
\hline \text { Eugene } & 178 & 199 & 128 & 47 & 453 & \_ & 91 & 110 & 64 & 181 \\
\hline \text { Newport } & 252 & 135 & 180 & 52 & 478 & 91 & \_ & 114 & 83 & 117 \\
\hline \text { Portland } & 285 & 95 & 160 & 84 & 344 & 110 & 114 & \_ & 47 & 78 \\
\hline \text { Salem } & 240 & 136 & 131 & 40 & 389 & 64 & 83 & 47 & \_ & 118 \\
\hline \text { Seaside } & 356 & 17 & 247 & 155 & 423 & 181 & 117 & 78 & 118 & \_ \\
\hline
\end{array}\)

Solution

Using Kruskal’s algorithm, we add edges from cheapest to most expensive, rejecting any that close a circuit. We stop when the graph is connected.

\(\begin{array}{ll} \text{Seaside to Astoria} & 17 \text{ miles} \\ \text{Corvallis to Salem} & 40 \text{ miles} \\ \text{Portland to Salem} & 47 \text{ miles} \\ \text{Corvallis to Eugene} & 47 \text{ miles} \\ \text{Corvallis to Newport} & 52 \text{ miles} \\ \text{Salem to Eugene} & \text{reject – closes circuit} \\ \text{Portland to Seaside} & 78 \text{ miles} \end{array}\)

The graph up to this point is shown to the right.

Continuing,

\(\begin{array}{ll} \text{Newport to Salem} & \text{reject} \\ \text{Corvallis to Portland} & \text{reject} \\ \text{Eugene to Newport} & \text{reject} \\ \text{Portland to Astoria} & \text{reject} \\ \text{Ashland to Crater Lk} & 108\text{ miles} \\ \text{Eugene to Portland} & \text{reject} \\ \text{Newport to Portland} & \text{reject} \\ \text{Newport to Seaside} & \text{reject} \\ \text{Salem to Seaside} & \text{reject} \\ \text{Bend to Eugene} & 128\text{ miles} \\ \text{Bend to Salem} & \text{reject} \\ \text{Astoria to Newport} & \text{reject} \\ \text{Salem to Astoria} & \text{reject} \\ \text{Corvallis to Seaside} & \text{reject} \\ \text{Portland to Bend} & \text{reject} \\ \text{Astoria to Corvallis} & \text{reject} \\ \text{Eugene to Ashland} & 178\text{ miles} \end{array}\)

This connects the graph. The total length of cable to lay would be 695 miles.

Try it Now 7

Find a minimum cost spanning tree on the graph below using Kruskal’s algorithm.

Answer

AB: Add, cost 11

BG: Add, cost 13

AE: Add, cost 14

AG: Skip, would create circuit ABGA

EF: Add, cost 16

EC: Add, cost 17

This completes the spanning tree