A tree is a connected acyclic graph. As a result, a tree with n vertices has n-1 edges:

In this example, there are 9 vertices:

{A, B, C, D, E, F, G, H, I}and 8 edges:

{{A,B},{B,D},{D,C},{D,E},{E,F},{E,H},{F,G},{H,I}}For any graph, it is possible to find a "

- Label the edges of the graph randomly using small positive integers for the weights.
- Starting with the edge or edges with the highest weights, delete each edge which does not disconnect the graph.
- Stop when there are n-1 edges left.

For example, let us begin with the following graph:

We assign a set of random weights to the edges:

The edges with the highest weights are {A,D} and {D,E}. Removal of the edge {D,E} would disconnect the graph, but we can remove the edge {A,D}:

Edges {A,B} and {E,G} have the next highest weights; of these, we can only remove {A,B} without disconnecting the graph:

The edges with the next highest weights are {A,C} and {C,D}. If we were to remove the edge {A,C}, vertex A would be disconnected from the graph, but we are able to remove the edge {C,D}:

The graph now has 6 edges:

{{A,C},{B,C},{B,D},{D,E},{E,F},{E,G}}Since both this and the original graph have 7 vertices, we have found a spanning tree:

By moving the vertex A, we can represent this spanning tree in planar form:

Click here to view another spanning tree constructed from the same graph. It is different because the weights were assigned differently.

Spanning trees are constructed by network switches (which control data transfers between network segments) in order to prevent data from moving along cycles in the network. The protocol for their cooperation in this regard is called "Spanning Tree Protocol" (or STP).

- ( x + 2 ) / ( y - 3 )The rooted tree which represents this expression is:

The root vertex of this tree is labeled with the division operator ("/"). Each edge is called a "

{x,2,y,3}are called the "

- the two vertices labeled with minus signs are at a depth of one;
- the vertices labeled {+,y,3} are at a depth of two,
- and the vertices {x,2} are at a depth of three.

This representation of the arithmetic expression is convenient because it graphically represents the order of operations in the expression:

- x+2 is performed first because it is at the deepest level;
- the unary minus -(x+2) is performed next, followed by
- y-3 (operations at the same level are usually performed from left to right),
- and finally the division is performed.

It is interesting to examine the tree corresponding to a very similar arithmetic expression such as

( - x + 2 ) / y - 3In this expression, the order of operations is

- - x
- - x + 2
- ( - x + 2 ) / y
- ( - x + 2 ) / y - 3 (or more clearly, (( - x + 2 ) / y ) - 3 )

The rooted tree corresponding to this expression is:

Rooted trees are also commonly used to represent the structure of file systems in a computer (often called the "

- C:\Program Files\Accessories\notepad.exe
- C:\Windows\ftp.exe
- C:\Program Files\Internet Explorer\iexplore.exe

The above expressions are called file "**path names**"; because of the graphical user interface
provided by Windows, you seldom need to know the file path names for the files you use. For instance, to
use the FTP program, you would first open the disk drive labeled C: (in My Computer on the desktop),
then open the folder labeled Windows,
and finally open the program FTP. The following rooted tree illustrates a portion of the Windows
file system; specifically, those portions which contain the files we have been discussing:

The ellipsis ("...") indicate large portions of the tree which have been omitted for space reasons; a typical Windows file system contains several hundred folders (also called directories) and several thousand files. The root vertex of this tree is labeled C:, and C:\ is called the "

emacs instead of notepad andIn the Linux system, these files have the path names

netscape instead of Internet Explorer.

- /usr/bin/emacs
- /usr/bin/ftp
- /usr/bin/netscape

A portion of the Linux directory tree illustrates their location:

Here, the root vertex is labeled "/"; / is the root directory of a UNIX file system. The vertices labeled emacs, ftp and netscape are actually the only leaves in this tree corresponding to files; the other vertices represent directories whose contents have again been omitted for lack of space.

{/,usr,bin,netscape}from the root vertex to the leaf vertex corresponding to the program file for netscape.

While our examples of graphs and trees so far have often implied an ordering of the vertices, the edges themselves have not contained any directional information. We move now to the subject of directed graphs, whose edges have direction.

Go to: Title Page Table of Contents Index

©2002, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.