12.11: Trees

Last updated
Save as PDF

Page ID: 129678

$ \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}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Figure 12.230 In graph theory, graphs known as trees have structures in common with live trees. (credit: “Row of trees in Roslev” by AKA CJ/Flickr, Public Domain)

Learning Objectives

After completing this section, you should be able to:

Describe and identify trees.
Determine a spanning tree for a connected graph.
Find the minimum spanning tree for a weighted graph.
Solve application problems involving trees.

We saved the best for last! In this last section, we will discuss arguably the most fun kinds of graphs, trees. Have you every researched your family tree? Family trees are a perfect example of the kind of trees we study in graph theory. One of the characteristics of a family tree graph is that it never loops back around, because no one is their own grandparent!

What Is A Tree?

Whether we are talking about a family tree or a tree in a forest, none of the branches ever loops back around and rejoins the trunk. This means that a tree has no cyclic subgraphs, or is acyclic. A tree also has only one component. So, a tree is a connected acyclic graph. Here are some graphs that have the same characteristic. Each of the graphs in Figure 12.231 is a tree.

Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z.

Figure 12.231 Graphs T, P, and S

Let’s practice determining whether a graph is a tree. To do this, check if a graph is connected and has no cycles.

Example 12.46

Identifying Trees

Identify any trees in Figure 12.232. If a graph is not a tree, explain how you know.

Three graphs. Graph M has 7 vertices. The edges are a b, b f, f g, f c, b c, b d, and d e. Graph N has 6 vertices. The edges are I j, I h, l k, and l m. The edges, I j, and l k intersect each other. Graph P has 6 vertices. The edges are s t, s r, r q, q p, and p o.

Figure 12.232 Graphs M, N, and P

Answer

Graph M is not a tree because it contains the cycle (b, c, f).
Graph N is not a tree because it is not connected. It has two components, one with vertices h, i, j, and another with vertices k, l, m.
Graph P is a tree. It has no cycles and it is connected.

Your Turn 12.46

There are some configurations that are commonly used when setting up computer networks. Several of them are shown in the given figure. Which of the configurations in the figure appear to have the characteristics of a tree graph? If a configuration does not appear to have the characteristics of a tree graph, explain how you know.

Four illustrations represent the common network configurations. The first illustration represents mesh topology. Six computers are interconnected. The second illustration represents a ring topology. Five computers are connected in a ring. The third illustration represents star topology. A computer at the center is connected to five computers surrounding it. The fourth illustration represents tree topology. Two branches arise from a horizontal bus. Each branch has a computer at the center connected to five computers surrounding it

Figure 12.233 Common Network Configurations

Types of Trees

Mathematicians have had a lot of fun naming graphs that are trees or that contain trees. For example, the graph in Figure 12.234 is not a tree, but it contains two components, one containing vertices a through d, and the other containing vertices e through g, each of which would be a tree on its own. This type of structure is called a forest. There are also interesting names for trees with certain characteristics.

A path graph or linear graph is a tree graph that has exactly two vertices of degree 1 such that the only other vertices form a single path between them, which means that it can be drawn as a straight line.
A star tree is a tree that has exactly one vertex of degree greater than 1 called a root, and all other vertices are adjacent to it.
A starlike tree is a tree that has a single root and several paths attached to it.
A caterpillar tree is a tree that has a central path that can have vertices of any degree, with each vertex not on the central path being adjacent to a vertex on the central path and having a degree of one.
A lobster tree is a tree that has a central path that can have vertices of any degree, with paths consisting of either one or two edges attached to the central path.

Examples of each of these types of structures are given in Figure 12.235.

Graph F has 8 vertices. The vertices are labeled a to h. Edges connect b a, b d, b c, f e, f h, and f g.

Figure 12.234 Forest Graph F

Six graphs. Graph S has 7 vertices. The edges are a b, b f, f g, f c, b c, b d, and d e. Graph N has 6 vertices. The edges are I j, I h, l k, and l m. The edges, I j, and l k intersect each other. Graph P has 6 vertices. The edges are s t, s r, r q, q p, and p o. Graph Z has 12 vertices. The edges are a b, a c, a d, a e, a f, a g, a h, h i, c j, e k, and k l. Graph C has 14 vertices. The edges are m n, n z, n o, o r, o p, o x, o y, p y, p x, p s, p t, p u, p q, p v, and p w. Graph L has 26 vertices. The edges are f q, f t, f s, f e, e o, e p, p z, e d, d m, m v, d n, n y, d c, c k, k u, c l, l k, c b, b i, i t, b j, j w, b a, b g, and b h.

Figure 12.235 Six Types of Trees

Example 12.47

Identifying Types of Trees

Each graph in Figure 12.236 is one of the special types of trees we have been discussing. Identify the type of tree.

Two graphs. Graph U has 17 vertices. The edges are o q, o p, o l, l n, l k, l m, l i, I j, I f, f g, f h, f d, d e, f b, b c, and b a. Graph V hs 6 vertices. The edges are r s, s t, t u, u v, and v w. The edges, s t and u v intersect.

Figure 12.236 Graphs U and V

Answer

Graph U has a central path a → b → d → f → i → l → o → q. Each vertex that is not on the path has degree 1 and is adjacent to a vertex that is on the path. So, U is a caterpillar tree.

Graph V is a path graph because it is a single path connecting exactly two vertices of degree one, r → s → u → v → w.

Your Turn 12.47

Of the network configurations from Figure 12.297, which, if any, has the characteristics of a

Star tree?

Caterpillar tree?

Path graph?

Characteristics of Trees

As we study trees, it is helpful to be familiar with some of their characteristics. For example, if you add an edge to a tree graph between any two existing vertices, you will create a cycle, and the resulting graph is no longer a tree. Some examples are shown in Figure 12.237. Adding edge bj to Graph T creates cycle (b, c, i, j). Adding edge rt to Graph P creates cycle (r, s, t). Adding edge tv to Graph S creates cycle (t, u, v).

Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. The edges, c i, and i j are in blue. A dashed edge connects b and j. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. The edges, t s, and s r are in blue. A dashed edge connects t and r. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. The edges, u t, and u v are in blue. A dashed edge connects t and v.

Figure 12.237 Adding Edges to Trees

It is also true that removing an edge from a tree graph will increase the number of components and the graph will no longer be connected. In fact, you can see in Figure 12.238 that removing one or more edges can create a forest. Removing edge qr from Graph P creates a graph with two components, one with vertices o, p and q, and the other with vertices r, s, and t. Removing edge uw from Graph S creates two components, one with just vertex w and the other with the rest of the vertices. When two edges were removed from Graph T, edge bf and edge cd, creates a graph with three components as shown in Figure 12.238.

Three graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. The edges, d c, and b f are in dashed lines. The graph is separated into three blocks. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. The edge, q r is in dashed lines. The graph is separated into two blocks. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. The edge, u w is in dashed lines. The graph is separated into two blocks.

Figure 12.238 Removing Edges from Trees

A very useful characteristic of tree graphs is that the number of edges is always one less than the number of vertices. In fact, any connected graph in which the number of edges is one less than the number of vertices is guaranteed to be a tree. Some examples are given in Figure 12.239.

Six graphs. Graph T has 15 vertices. The edges are as follows: a b, b c, c d, c i, i j, j k, k o, d e, d l, e n, e m, b f, f g, and g h. Graph P has 6 vertices. The edges are as follows: t s, s r, r q, q p, and p o. Graph S has 7 vertices. The edges are as follows: u t, u v, u w, u x, u y, and u z. Graph Z has 12 vertices. The edges are a b, a c, a d, a e, a f, a g, a h, h i, c j, e k, and k l. Graph C has 14 vertices. The edges are m n, n z, n o, o r, o p, o x, o y, p y, p x, p s, p t, p u, p q, p v, and p w. Graph L has 26 vertices. The edges are f q, f t, f s, f e, e o, e p, p z, e d, d m, m v, d n, n y, d c, c k, k u, c l, l k, c b, b i, i t, b j, j w, b a, b g, and b h.

Figure 12.239 Number of Vertices and Edges in Trees vs. Other Graphs

FORMULA

The number of edges in a tree graph with $n$ vertices is $n - 1$ .

A connected graph with n vertices and $n - 1$ edges is a tree graph.

Example 12.48

Exploring Characteristics of Trees

Use Graphs I and J in Figure 12.240 to answer each question.

Two graphs. Graph I has six vertices: a, b, c, d, e, and f. Edges connect a b, b c, b e, d e, and e f. Graph J has seven vertices: g h, i, j, k, l, and m. Edges connect g h, h i, j h, j l, k l, and l m.

Figure 12.240 Graphs I and J

Which vertices are in each of the components that remain when edge be is removed from Graph I?
Determine the number of edges and the number of vertices in Graph J. Explain how this confirms that Graph J is a tree.
What kind of cycle is created if edge im is added to Graph J?

Answer

When edge be is removed, there are two components that remain. One component includes vertices a, b, and c. The other component includes vertices d, e, and f.
There are seven vertices and six edges in Graph J. This confirms that Graph J is a tree because the number of edges is one less than the number of vertices.
The pentagon (i, h, j, l, m) is created when edge im is added to Graph J.

Your Turn 12.48

Use Graphs I and J in Figure 12.301 to answer each question.

Which vertices are in each of the components that remain when edge jl is removed from Graph J?

Determine the number of edges and the number of vertices in Graph I. Explain how this confirms that Graph I is a tree.

What kind of cycle is created if edge cf is added to Graph I?

Who Knew?

Graph Theory in the Movies

In the 1997 film Good Will Hunting, the main character, Will, played by Matt Damon, solves what is supposed to be an exceptionally difficult graph theory problem, “Draw all the homeomorphically irreducible trees of size $n = 10$ .” That sounds terrifying! But don’t panic. Watch this great Numberphile video to see why this is actually a problem you can do at home!

Video

The Problem in Good Will Hunting by Numberphile

Spanning Trees

Suppose that you planned to set up your own computer network with four devices. One option is to use a “mesh topology” like the one in Figure 12.241, in which each device is connected directly to every other device in the network.

Figure 12.241 Common Network Configurations

The mesh topology for four devices could be represented by the complete Graph A₁ in Figure 12.242 where the vertices represent the devices, and the edges represent network connections. However, the devices could be networked using fewer connections. Graphs A₂, A_3, and A₄ of Figure 12.242 show configurations in which three of the six edges have been removed. Each of the Graphs A₂, A₃ and A₄ in Figure 12.242 is a tree because it is connected and contains no cycles. Since Graphs A₂, A₃ and A₄ are also subgraphs of Graph A₁ that include every vertex of the original graph, they are also known as spanning trees.

Four graphs. Graph A 1 has four vertices: a, b, c, and d. The edges are a b, b d, d c, c a, a d, and b c. Graph A 2 has four vertices: a, b, c, and d. The edges are a b, b c, and c d. Graph A 3 has four vertices: a, b, c, and d. The edges are a b, a c, and c d. Graph A 4 has four vertices: a, b, c, and d. The edges are a b, a c, and a d.

Figure 12.242 Network Configurations for Four Devices

By definition, spanning trees must span the whole graph by visiting all the vertices. Since spanning trees are subgraphs, they may only have edges between vertices that were adjacent in the original graph. Since spanning trees are trees, they are connected and they are acyclic. So, when deciding whether a graph is a spanning tree, check the following characteristics:

All vertices are included.
No vertices are adjacent that were not adjacent in the original graph.
The graph is connected.
There are no cycles.

Example 12.49

Identifying Spanning Trees

Use Figure 12.243 to determine which of graphs M₁, M₂, M₃, and M₄, are spanning trees of Q.

Five graphs. Graph Q has six vertices: a, b, c, d, e, and f. The edges are a b, a c, a d, b d, d f, c d, c e, c f, and e f. Graph M 1 has six vertices: a, b, c, d, e, and f. The edges are a b, b d, d c, c e, f, and f d. Graph M 2 has six vertices: a, b, c, d, e, and f. The edges are a b, a d, d f, f e, and e c. Graph M 3 has six vertices; a, b, c, d, e, and f. The edges are b d, d f, a f, f e, and e c. Graph M 4 has six vertices: a, b, c, d, e, and f. The edges are a b, c e, e f, and f d.

Figure 12.243 Graphs Q, M₁, M₂, M_3, and M₄

Answer

Graph M₁ is not a spanning tree of Graph Q because it has a cycle (c, d, f, e).
Graph M₂ is a spanning tree of Graph Q because it has all the original vertices, no vertices are adjacent in M₂ that weren’t adjacent in Graph Q, Graph M₂ is connected and it contains no cycles.
Graph M₃ is not a spanning tree of Graph Q because vertices a and f are adjacent in Graph M₃ but not in Graph Q.
Graph M₄ is not a spanning tree of Graph Q because it is not connected.

So, only graph M₂ is a spanning tree of Graph Q.

Your Turn 12.49

Use the given figure for the following exercises.

Five graphs. Graph H has five vertices: n, q, r, s, and t. The edges are p q, p r, q r, q t, r t, r s, and s t. Graph N 1 has four vertices: p, q, s, and t. The edges are p t, q s, and s t. Graph N 2 has five vertices: p, q, r, s, and t. The edges are p r, q r, r s, r t, and s t. Graph N 3 has five vertices: p, q, r, s, and t. The edges are p q, q r, r s, and qt. Graph N 4 has five vertices: p, q, r, s, and t. The edges are p q, r s, and s t.

Figure 12.244

Since sq is not an edge in Graph H, Graph N₁ cannot be a spanning tree of H.

True
False

Graph N₂ is a spanning tree of Graph H.

True
False

Graph N₃ is a spanning tree of Graph H.

True
False

Since there is no path between p and t in Graph N₄, it cannot be a spanning tree of any graph.

True
False

Constructing a Spanning Tree Using Paths

Suppose that you wanted to find a spanning tree within a graph. One approach is to find paths within the graph. You can start at any vertex, go any direction, and create a path through the graph stopping only when you can’t continue without backtracking as shown in Figure 12.245.

A graph with 23 vertices and 35 edges. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here.

Figure 12.245 First Phase to Construct a Spanning Tree

Once you have stopped, pick a vertex along the path you drew as a starting point for another path. Make sure to visit only vertices you have not visited before as shown in Figure 12.246.

A graph with 23 vertices and 35 edges. Ten edges are highlighted in blue. Ten edges are highlighted in green. Two vertices are labeled started here and stopped here.

Figure 12.246 Intermediate Phase to Construct a Spanning Tree

Repeat this process until all vertices have been visited as shown in Figure 12.247.

Figure 12.247 Final Phase to Construct a Spanning Tree

The end result is a tree that spans the entire graph as shown in Figure 12.248.

Figure 12.248 The Resulting Spanning Tree

Notice that this subgraph is a tree because it is connected and acyclic. It also visits every vertex of the original graph, so it is a spanning tree. However, it is not the only spanning tree for this graph. By making different turns, we could create any number of distinct spanning trees.

Example 12.50

Constructing Spanning Trees

Construct two distinct spanning trees for the graph in Figure 12.249.

Graph L has 11 vertices and 19 edges. The graph resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines.

Figure 12.249 Graph L

Answer

Two possible solutions are given in Figure 12.250 and Figure 12.251.

Two graphs depict removing edges from graph L. The first graph has 11 vertices and 19 edges. It resembles a square resting below a triangle on either side. The triangles are connected via a trapezoid. The squares have diagonal lines. 6 edges are in green, 2 edges are in purple, and 2 edges are in blue. Green represents phase 1, blue represents phase 2, and purple represents phase 3. The second graph is the final tree. The black edges from the first graph are removed.

Figure 12.250 First Spanning Tree for Graph L

Figure 12.251 Second Spanning Tree for Graph L

Your Turn 12.50

Construct three distinct spanning trees for Graph J.

Figure 12.252 Graph J

Revealing Spanning Trees

Another approach to finding a spanning tree in a connected graph involves removing unwanted edges to reveal a spanning tree. Consider Graph D in Figure 12.253.

Graph D has 10 vertices. The vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and I j.

Figure 12.253 Graph D

Graph D has 10 vertices. A spanning tree of Graph D must have 9 edges, because the number of edges is one less than the number of vertices in any tree. Graph D has 13 edges so 4 need to be removed. To determine which 4 edges to remove, remember that trees do not have cycles. There are four triangles in Graph D that we need to break up. We can accomplish this by removing 1 edge from each of the triangles. There are many ways this can be done. Two of these ways are shown in Figure 12.254.

Four graphs depict removing edges from graph D. In the first graph, the vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and i j. The edges, a c, e f, g h, and b j are shown in dashed lines. The second graph is the same as that of the first with edges, a c, e f, g h, and b j removed. In the third graph, the vertices are labeled from a to j. The edges are c d, c a, d a, a g, a h, g h, a b, b e, b f, e f, b i, b j, and i j. The edges, a c, a g, b f, and b i are shown in dashed lines. The fourth graph is the same as that of the first with edges, a c, a g, b f, and b i removed.

Figure 12.254 Removing Four Edges from Graph D

Video

Spanning Trees in Graph Theory

Example 12.51

Removing Edges to Find Spanning Trees

Use the graph in Figure 12.255 to answer each question.

Graph V has 9 vertices. The vertices are labeled from a to i. The edges are f c, f a, c a, c d, d a, a b, b e, e h, h i, I g, and g b.

Figure 12.255 Graph V

Determine the number of edges that must be removed to reveal a spanning tree.
Name all the undirected cycles in Graph V.
Find two distinct spanning trees of Graph V.

Answer

Graph V has nine vertices so a spanning tree for the graph must have 8 edges. Since Graph V has 11 edges, 3 edges must be removed to reveal a spanning tree.
(a, c, d), (a, c, f), (a, d, c, f), and (b, e, h, i, g)
To find the first spanning tree, remove edge ac, which will break up both of the triangles, remove edge cf , which will break up the quadrilateral, and remove be, which will break up the pentagon, to give us the spanning tree shown in Figure 12.256.

Figure 12.256 Spanning Tree Formed Removing ac, cf, and be

To find another spanning tree, remove ad, which will break up (a, c, d) and (a, d, c, f), remove af to break up (a, c, f), and remove hi to break up (b, e, h, i, g). This will give us the spanning tree in Figure 12.257.

Figure 12.257 Spanning Tree Formed Removing ad, af, and hi

Your Turn 12.51

Name three edges that you could remove from Graph V in Figure 12.316 to form a third spanning tree, different from those in the solution to Example 12.50 Exercise 3.

Who Knew?

Chains of Affection

Here is a strange question to ask in a math class: Have you ever dated your ex’s new partner’s ex? Research suggests that your answer is probably no. When researchers Peter S. Bearman, James Moody, and Katherine Stovel attempted to compare the structure of heterosexual romantic networks at a typical midwestern high school to simulated networks, they found something surprising. The actual social networks were more like spanning trees than other possible models because there were very few short cycles. In particular, there were almost no four-cycles.

A graph with four vertices. The vertices are Bob, Alice, Carol, and Ted. A double-headed arrow labeled time 1 is between Bob and Carol. A double-headed arrow labeled time 1 is between Alice and Tex. A double-headed arrow labeled time 2 is between Carol and Ted. A double-headed arrow labeled with a question mark is between Bob and Alice.

Figure 12.258 Chains of Affection

“…the prohibition against dating (from a female perspective) one’s old boyfriend’s current girlfriend’s old boyfriend – accounts for the structure of the romantic network at [the highschool].”

In their article “Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks,” the researchers went on to explain the implications for the transmission of sexually transmitted diseases. In particular, social structures based on tree graphs are less dense and more likely to fragment. This information can impact social policies on disease prevention. (Peter S. Bearman, James Moody, and Katherine Stovel, “Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks,” American Journal of Sociology Volume 110, Number 1, pp. 44-91, 2004)

Kruskal’s Algorithm

In many applications of spanning trees, the graphs are weighted and we want to find the spanning tree of least possible weight. For example, the graph might represent a computer network, and the weights might represent the cost involved in connecting two devices. So, finding a spanning tree with the lowest possible total weight, or minimum spanning tree, means saving money! The method that we will use to find a minimum spanning tree of a weighted graph is called Kruskal’s algorithm. The steps for Kruskal’s algorithm are:

Step 1: Choose any edge with the minimum weight of all edges.

Step 2: Choose another edge of minimum weight from the remaining edges. The second edge does not have to be connected to the first edge.

Step 3: Choose another edge of minimum weight from the remaining edges, but do not select any edge that creates a cycle in the subgraph you are creating.

Step 4: Repeat step 3 until all the vertices of the original graph are included and you have a spanning tree.

Video

Use Kruskal's Algorithm to Find Minimum Spanning Trees in Graph Theory

Example 12.52

Using Kruskal’s Algorithm

A computer network will be set up with six devices. The vertices in the graph in Figure 12.259 represent the devices, and the edges represent the cost of a connection. Find the network configuration that will cost the least. What is the total cost?

A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars.

Figure 12.259 Graph of Network Connection Costs

Answer

A minimum spanning tree will correspond to the network configuration of least cost. We will use Kruskal’s algorithm to find one. Since the graph has six vertices, the spanning tree will have six vertices and five edges.

Step 1: Choose an edge of least weight. We have sorted the weights into numerical order. The least is $100. The only edge of this weight is edge AF as shown in Figure 12.260.

Figure 12.260 Step 1 Select Edge AF

Step 2: Choose the edge of least weight of the remaining edges, which is BD with $120. Notice that the two selected edges do not need to be adjacent to each other as shown in Figure 12.261.

Figure 12.261 Step 2 Select Edge BD

Step 3: Select the lowest weight edge of the remaining edges, as long as it does not result in a cycle. We select DF with $150 since it does not form a cycle as shown in Figure 12.262.

Figure 12.262 Step 3 Select Edge DF

Repeat Step 3: Select the lowest weight edge of the remaining edges, which is BE with $160 and it does not form a cycle as shown in Figure 12.263. This gives us four edges so we only need to repeat step 3 once more to get the fifth edge.

Figure 12.263 Repeat Step 3 Select Edge DF

Repeat Step 3: The lowest weight of the remaining edges is $170. Both BF and CE have a weight of $170, but BF would create cycle (b, d, f) and there cannot be a cycle in a spanning tree as shown in Figure 12.264.

Figure 12.264 Repeat Step 3 Do Not Select Edge BF

So, we will select CE, which will complete the spanning tree as shown in Figure 12.265.

Figure 12.265 Repeat Step 3 Select Edge CE

The minimum spanning tree is shown in Figure 12.266. This is the configuration of the network of least cost. The spanning tree has a total weight of $$ 100 + $ 120 + $ 150 + $ 160 + $ 170 = $ 700$ , which is the total cost of this network configuration.

A graph has six vertices labeled A to F. The edges are as follows. A F, curved edge, 100 dollars. B E, 160 dollars. B D, 120 dollars. C E, 170 dollars. D F, 150 dollars.

Figure 12.266 Final Minimum Spanning Tree

Your Turn 12.52

Find a minimum spanning tree for the weighted graph. Give its total weight.

A weighted graph with five vertices. The vertices are as follows: U, V, W, X, and Z. The edges are labeled as follows. U V, 89. V Y, 24. Y X, 68. X W, 45. W U, 37. U X, 49. W V, 68.

Figure 12.267 Weighted Graph

Check Your Understanding

85.

The number of cycles in a spanning tree is one less than the number of vertices.

True
False

86.

A spanning tree contains no triangles.

True
False

87.

A spanning tree includes every vertex of the original graph.

True
False

88.

There is a unique path between each pair of vertices in a spanning tree.

True
False

89.

A spanning tree must be connected.

True
False

90.

Kruskal’s algorithm is a method for finding all the different spanning trees in a given graph.

True
False

91.

Only graphs that are trees have spanning trees.

True
False

92.

A minimum spanning tree of a given graph can be found using Kruskal’s algorithm.

True
False

93.

A minimum spanning tree of a given graph is the subgraph, which is a tree, includes every vertex of the original graph, and which has the least weight of all spanning trees.

True
False

94.

If a graph contains any cut edges, they must be included in any spanning tree.

True
False

Section 12.10 Exercises

For the following exercises, refer to the figure shown.
$Four graphs. Graph M has 5 vertices: p, q, t, u, and r. The edges are q t, p u, and u r. Graph W has 11 vertices: a to k. the edges are a e, a f, a b, b g, b h, b c, c i, c d, c k, a j, and j k. Graph R has 7 vertices: a, b, c, d, e, f, and h. The curved edges are a b, b c, c d, d e, and e f. A straight edge connects b and h. Graph X has 10 vertices: a to j. The edges are b a, b c, b d, b i, b f, i e, i g, i h, and i j.$

Which graphs, if any, are trees?

Which graphs, if any, are not trees because they are not connected?

Which graphs, if any, are not trees because they contain a cycle?

For the following exercises, refer to the figure shown. Identify any graphs that fit the given description.
$Six graphs. Graph T 1 has 16 vertices labeled from a, b, c, d, e, f, g, h, I, j, k, m, n, o, r, and s. The edges are b d, b c, b a, a n, b r, b f, r s, r i, e o, o i, i j, j k, i h, i g, and g m. Graph T 2 has 6 vertices: a to f. The edges are a b, a c, a d, a e, and a f. Graph T 3 has 11 vertices: a to k. The edges are b d, f k, k b, b i, i c, a j, j b, b h, h g, and g e. Graph T 4 has 8 vertices: a to h. The edges are a b, b c, c d, d e, e f, f g, and g h. Graph T 5 has 15 vertices: a to o. The edges are a b, b c, b d, b e, e f, e g, e h, e i, e m, m j, m k, m l, m n, and n o. Graph T 6 has 10 vertices: a to j. The edges are a b, a c, a d, a e, a f, j h, h g, and h i.$

Tree graph

Star graph

Star like graph

Line graph (or path graph)

Lobster graph

Caterpillar graph

10.

Forest graph

For the following exercises, use the figure shown to answer the questions.
$Two graphs. Graph H has 7 vertices: a to g. The edges are a b, a e, b d, e d, d c, d f, f g, and c g. Graph Q has 7 vertices: h to n. The edges are h i, h j, I j, I k, k m, m n, m l, k l, and n l.$

11.

Determine whether Graph H₁ is a spanning tree of Graph H. If not, explain how you know.
$Graph H 1 has 7 vertices labeled from a to g. The edges are a b, b d, e d, d f, f g, and g c.$

12.

Determine whether Graph H₂ is a spanning tree of Graph H. If not, explain how you know.
$Graph H 2 has 7 vertices labeled from a to g. The edges are a e, e d, d b, d c, c f, and f g.$

13.

Determine whether Graph H₃ is a spanning tree of Graph H. If not, explain how you know.
$Graph H 3 has 7 vertices labeled from a to g. The edges are a b, a e, c d, d f, and c g.$

14.

Determine whether Graph Q₁ is a spanning tree of Graph Q. If not, explain how you know.
$Graph Q 1 has 7 vertices labeled from h to n. The edges are j h, h i, I k, k l, k m, l m, and m n.$

15.

Determine whether Graph Q₂ is a spanning tree of Graph Q. If not, explain how you know.
$Graph Q 2 has 7 vertices labeled from h to m. The edges are j h, h i, I k, k m, and m l.$

16.

Determine whether Graph Q₃ is a spanning tree of Graph Q. If not, explain how you know.
$Graph Q 3 has 7 vertices labeled from h to m. The edges are h i, I j, I k, k l, l m, and l n.$

For the following exercises, a student has been asked to construct a spanning tree for Graph O, as shown in the figure. The dashed lines show the first step that the student took, creating a path from vertex h to vertex d.
$Graph O has eight vertices labeled from a to h. The edges are as follows: a f, a e, g f, g e, g h, h e, e f, f b, b c, f c, c d, f d, and d e. The edges, h e, e f, f b, b c, and c d are in dashed lines.$

17.

How many more edges must be included with the dashed edges to create a spanning tree?

18.

List three unused (solid) edges from Graph O that cannot be used to complete the spanning tree.

19.

Give an example of a set of edges that do not have e as an endpoint, which would complete the spanning tree.

20.

Give an example of a set of edges that do not have f as an endpoint, which would complete the spanning tree.

For the following exercises, a student has been asked to construct a spanning tree for Graph O, as shown in the figure. The dashed lines show the first step that the student took, creating a path from vertex c to vertex h.
$Graph O has eight vertices labeled from a to h. The edges are as follows: a f, a e, g f, g e, g h, h e, e f, f b, b c, f c, c d, f d, and d e. The edges, g f, g e, e h, and f c are in dashed lines.$

21.

How many more edges must be included with the dashed edges to create a spanning tree?

22.

List two unused edges from Graph O that cannot be used to complete the spanning tree.

23.

Give an example of a set of edges that do not have f as an endpoint, which would complete the spanning tree.

24.

Give an example of a set of edges that have neither c nor e as an endpoint, which would complete the spanning tree.

For the following exercises, use Graphs A, B, and C.
$Three graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. Edges connect s t, t v, v w, w x, x u, w u, u s, and u t.$

25.

How many edges must be removed from Graph A to create a spanning tree?

26.

How many edges must be removed from Graph B to create a spanning tree?

27.

How many edges must be removed from Graph C to create a spanning tree?

28.

Identify all the distinct cyclic subgraphs of Graph A.

29.

Identify all the cyclic subgraphs of Graph B.

30.

Identify all the cyclic subgraphs of Graph C.

31.

Draw four spanning trees of Graph A each of which includes edges vs, uv, wz and xy.

32.

Draw four spanning trees of Graph B which includes edge ut, but not ur.

33.

Draw four spanning trees of Graph C that each have only one edge with an endpoint at vertex u.

For the following exercises, use the figure shown. Draw a graph that fits the given description.
$Four graphs. Each graph has four vertices: a, b, c, and d. The first graph shows the following edges: a c, c d, and c b. The second graph shows the following edges: a b, b d, and d c. The third graph shows the following edges: b a, a c, and cd. The fourth graph shows the following edges: a d, b d, and c d.$

34.

S₁, S₂, S₃ and S₄ are all spanning trees.

35.

S₁ and S₂ are spanning trees, but S₄ is not.

36.

S₃ and S₄ are spanning trees but S₁ is not.

37.

S₂ and S₃ are spanning trees but S₁ is not.

38.

S₂ and S₃ are spanning trees but S₄ is not.

39.

S₁, S_2, and S₃ are spanning trees but S₄ is not.

40.

S₂, S₃, and S₄ are spanning trees but S₁ is not.

41.

S₁ and S₄ are spanning trees but S₂ and S₃ are not.

For the following exercises, use the figure shown to find the weight of the given spanning tree.
$Graph Z has nine vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows. 1, q to t. 2, s to v. 3, r to s. 4, q to u. 5, u to y. 6, r to v. 7, r to u. 8, v to y. 9, w to x. 10, x to y. 1, u to x. 12, t to w. 13, q to r. 14, t to u. 15, u to v.$

42.

$A graph has 9 vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows: q u, r u, r s, t u, u v, t w, u x, and x y.$

43.

$A graph has 9 vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows: q r, r u, r s, t u, u v, t w, w x, and v y.$

44.

$A graph has 9 vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows: q r, r s, r u, t u, u v, u x, w x, and x y.$

45.

Use Kruskal’s algorithm to draw a minimum spanning tree for Graph Z in the provided figure. Find its weight.

For the following exercises, draw a minimum spanning tree for the given graph, and calculate its weight.
$Four graphs. Graph A has four vertices: a, b, c, and d. The edges are labeled as follows: a b, 3; b d, 3; d c, 1; c a, 2; a d, 1; b c, 2. Graph B has five vertices: e, f, g, h, and i. The edges are labeled as follows: e f, 2-thirds; f g, 5-twelfths; g h, 1-twelfth; h i, 3-fourths; i e, 1-fourth; e h, 1-half; eg, 1-sixth; f i, -third; f h, 5-sixths; g i, 1. Graph C has five vertices: i, j, k, m, and n. The curved edges are labeled as follows: km, 20; m n, 30; n j, 40; j i, 50; i k, 10. The straight edges are labeled as follows: k j, 90; k n, 60; m i, 100; m j, 70; n i, 80. Graph d has four vertices; o, p, q, and r. The edges are labeled as follows: o p, 1.7; p q, 4.3; q r, 3.5; r o, 2.9 p r, 3.; o p, 1.2.$

46.

Graph A

47.

Graph C

48.

Graph B

49.

Graph D

For the following exercises, draw a weighted graph to represent the given information. Then use the graph to find a minimum spanning tree and give its weight. Explain what the weight represents in the given scenario.

50.

City planners are tasked with building roadways to connect locations A, B, C, and D. The cost to build the roadways between any given pair of locations is given in the table.

	A	B	C	D
A	-	125	320	275
B	125	-	110	540
C	320	110	-	1,010
D	275	540	1,010	-

Construction Costs in Thousands between Locations

51.

In a video game, the goal is to visit five different lands, V, W, X, Y and Z, without losing all your lives. The paths between the lands are rated for danger, 1 being lowest and 10 being highest. Once a path has been traversed successfully, it is free from danger. The ratings are given in the table.

	V	W	X	Y	Z
V	-	2	4	9	10
W	2	-	6	8	No Path
X	4	6	-	7	No Path
Y	9	8	7	-	5
Z	10	No Path	No Path	5	-

Danger Ratings between Lands

Search

Text Color

Text Size

Margin Size

Font Type

Example 12.46

Your Turn 12.46

Example 12.47

Identifying Types of Trees

Your Turn 12.47

FORMULA

Example 12.48

Exploring Characteristics of Trees

Your Turn 12.48

Who Knew?

Graph Theory in the Movies

Video

Spanning Trees

Example 12.49

Identifying Spanning Trees

Your Turn 12.49

Constructing a Spanning Tree Using Paths

Example 12.50

Constructing Spanning Trees

Your Turn 12.50

Revealing Spanning Trees

Video

Example 12.51

Removing Edges to Find Spanning Trees

Your Turn 12.51

Who Knew?

Chains of Affection

Kruskal’s Algorithm

Video

Example 12.52

Using Kruskal’s Algorithm

Your Turn 12.52

Check Your Understanding

Section 12.10 Exercises