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.

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

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.

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

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.