Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

6.7: Spanning Trees

  • Page ID
    34210
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    gt52.svgA 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.

    gt53.svg

    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

    gt54.svgUsing 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.

    gt55.svg\(\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,

    gt56.svg\(\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.

    gt57.svg

    Answer

    gt60.svgAB: 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


    6.7: Spanning Trees is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by David Lippman via source content that was edited to conform to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.