Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

16.5: Spanning Trees

( \newcommand{\kernel}{\mathrm{null}\,}\)

Definition: Spanning Subgraph

a subgraph that contains all the vertices of the parent graph

Definition: Spanning Tree

a spanning subgraph that is a tree

Example 16.5.1: Spanning trees for the complete graph K4.

Here is the complete graph with four vertices.

clipboard_ee07456c88c78a56d109cb8a979c7bbbd.png
Figure 16.5.1

And here are ten different spanning trees for K4.

clipboard_ec9ce4c5f954f1b8123bfeed7c4c26a52.png
Figure 16.5.2

If we carry out either of the depth-first or breadth-first search algorithms, but aren't looking for a path between specific vertices, the end result will be a spanning tree for the original graph.

Definition: Depth-first Spanning Tree

the result of performing the depth-first search algorithm on a graph, continuing until all vertices in the original graph appear in the search tree

Definition: Breadth-first Spanning Tree

the result of performing the breadth-first search algorithm on a graph, continuing until all vertices in the original graph appear in the search tree

Example 16.5.2: Depth-first and breadth-first spanning trees.

Figure 16.5.3 contains depth-first and breadth-first spanning trees for the graph in Figure 16.4.2, our source of examples for depth-first search (Example 16.4.1) and breadth-first search (Example 16.4.2).

clipboard_e9a2cf02a53cfa4e476bd808c149d14af.png
(a) Depth-first spanning tree for the graph in Figure 16.4.1.
clipboard_ed4d851cc8e6dcfcd68cc0ac4d470af16.png
(b) Breadth-first spanning tree for the graph in Figure 16.4.1.
Figure 16.5.3: Examples of depth- and breadth-first spanning trees.

This page titled 16.5: Spanning Trees is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?