For example, a mathematical path might resemble:

.

The everyday use of the word path might evoke an image resembling:

There is a correspondence between the mathematical meaning of path, and the image evoked by the everyday sense of the word path. In this instance, the vertices are given by the trail marker sings, and the edges are given by the sections of the trail joining the trail markers.

As you might expect, it is possible to see associations between the mathematical meaning of the word tree and the images evoked by the everyday meaning of the word tree.

A tree is basically a graph that can be drawn to look something like:

.

In my mind, the everyday meaning of the word tree evokes an image like:

.

Drawing vertices (in yellow) at the ends of the branches, and at the places where branches split gives a picture like:

.

The branches of the (everyday meaning) tree can then be used for the edges of the (mathematical meaning) tree (the trunk of the tree doesn't connect two vertices, so it can't be used as an edge).

So, the mathematical meaning of the word tree can be related quite directly to the 'everyday' meaning of the word tree. However, this does not (at least in my mind) suggest what (mathematical) trees might be useful for.

An Application for Trees: Sorting Algorithms

A sorting algorithm is an outline or description of a procedure for arranging data in a particular order. For example, you might (like me!) have trouble remembering important information like people's birthdays, and keep a card file.

This file isn't very organized at the moment - you might end up having to go through every person's card to find the one you are looking for. To me, the most immediate way of organizing this file would be to arrange it in alphabetical order, by last name.

For a file of only six cards, you could just pick them all up, and put them back in the file box in alphabetical order. If your file had thousands of cards, then you would have to be more systematic. For example, you could go through the cards, comparing each card with the one immediately behind it. If the cards are out of alphabetical order, then you would switch them.

This kind of sorting algorithm, where you compare the cards pair by pair and swap them if the pair is not in alphabetical order is often called a bubble sort. As you can probably anticipate, bubble sorting is a tedious and time-consuming process (even for a computer).

Trees can be used to sort the cards into alphabetical order in fewer steps. The idea behind using trees to sort a list of cards is to split the collection of cards into a lot of smaller collections, and then to split these into even smaller collections. For example, with the file of cards used to illustrate the bubble sort, the collection can be split up as shown below.

To sort the cards, the tree is turned upside down, and the cards recombined into steadily larger and larger collections. When collections of cards are put together, they are merged so that the resulting collection is in alphabetical order. When the process has run right down to the base or trunk of the tree, then you have the collection of cards that you started with, except that they are now in alphabetical order.

The mathematical definitions of trees and forests are given below. See if you can see how these definitions and the everyday notions of tree and forest correspond to each other.

Definition A forest is defined to be a graph that contains no circuits. A tree is a connected forest.

Each connected component in this forest is a tree. Do the connected components of forests have to be trees? Can you give an argument or an example to support your conclusions?

Theorem Suppose that T is a graph with n vertices. The following statements are equivalent:

1. T is a tree.

2. T has n- 1 edges and no circuits.

3. T is connected and has n- 1 edges.

4. T is connected and each of its edges is an isthmus.

5. Any two vertices of T are connected by exactly one simple path.

6. T has no circuits, but the addition of any new edge creates exactly one circuit.

Note The theorem states that all of the statements are equivalent. Two statements, A and B, are equivalent provided that statement A is true if and only if B is true. This is another one of those "double barreled" statements, where you have to prove "both barrels" in order to prove the theorem. In this case, we would have to show that if statement 1 is true, then statement 2 is true. Then, to do the other "barrel" of the proof, we'd have to show that if statement 2 is true, then statement 1 is true. This would have to be repeated for every pair of distinct statements in the theorem, and would amount to 30 little proofs that together constitute the proof of the theorem. This would be a pretty big job!

With a little organization, the proof of the theorem can be cut down to just proving six little proofs; that if statement 1 is true then statement 2 is true, if statement 2 is true then statement 3 is true, and so on, concluding with the proof that if statement 6 is true, then statement 1 is true. The proof ends up as a cycle of logical inferences.

Proof If n = 1, all six results are trivially true. So, assume n>= 2.
Use induction. Suppose the result is true for all graphs with fewer with n vertices.

Remove any edge, say from v to w. In the resulting graph, v and w lie in distinct connected components, A and B (each connected component is circled in the above diagram). Each of these connected components is a tree, say on r and s vertices respectively. A has r 1, and B has s 1 edges. Therefore, T has

T is connected and has n - 1 edges. Let e be any edge of T. Remove e and you get a graph with n vertices and n - 2 edges. But such a graph cannot be connected (i.e. start with any vertex on its own, then the addition of each edge in turn adds one new vertex to the connected component containing v. As there are only n - 2 edges, the connected component containing v has at most n - 1 vertices. Therefore the graph is disconnected). As e was an arbitrary edge, then every edge of T disconnects T.

T is connected and every edge is an isthmus. Let v and w be any two vertices of T. T is connected, so there is a simple path from v to w. Assume that there are 2 or more such paths. Then the removal of any edge of the second path that is not part of the first path does not disconnect the graph, T. Therefore, that edges removed was not an isthmus, giving a contradiction. Therefore, there is only one simple path from v to w in T.

Every two vertices are connected by a simple path. If T contained a circuit, then any two vertices in this circuit must be connected by at least two simple paths, contradicting 5, implying that T can contain no circuit. Add a new edge, say from x to y. This creates a circuit because x and y are already connected in T. If more than one circuit was created, then x and y would have to be joined by two or more paths in T, which is not the case, so only one circuit is created.

T has no circuits, but the addition of any edge creates exactly one circuit. Must prove that T is connected. Let v and w be any vertices of T. If no edge exists from v to w then add such an edge and you obtain a circuit. If you then remove this edge, then you'll be left with a path from x to y in T, so T is connected.

This completes the proof of the theorem.

In the proof , of the proof says to 'use induction.' Can you identify that way that mathematical induction has been used in that step of the proof, and relate it to other uses of Mathematical induction that have appeared in other lessons?

Following are a pair of corollaries to the theorem. These corollaries will be used later in this lesson, and in subsequent lessons.

Corollary Any forest with n vertices and k connected components has n- k edges.

Proof Suppose that the j^th connected component has n_j vertices then it has n_j- 1 edges. Therefore the forest has,

This concludes the proof of the corollary.

Corollary Every finite tree on two or more vertices has at least two vertices of degree one.

Now, T is connected, so for every v an element of V(T), d(v) >= 1. If every vertex had degree 2 or greater, then the average degree of the vertices would be greater than or equal to 2. Since the average degree is less than 2, at least one vertex must have degree 1.

Subtrees and Spanning Trees

Definition A subtree of a graph G is any subgraph of G that is a tree. A sub-forest is any subgraph of G that is a forest.

Definition If G is a connected graph, then a spanning tree for G is any subgraph of G that is a tree, and includes every vertex of G.

Example One pictorial representation of the cube graph is:

.

A spanning tree for the cube graph is:

Coloring the vertices and edges shows how the spanning tree relates to the

original cube graph.

Proposition For n>= 2, the complete graph on n vertices (i.e. K_n) has n^n-2 different spanning trees.

Hint: You might approach this proof by examing the first few cases of the proposition (n = 2, n = 3, etc.) and then try to use the technique of proof by induction.

Definition Any vertex, v, of a connected graph G with the property that the maximum distance from v to any other vertex is as small as possible is called a central vertex (or a center of the graph G). That maximum distance is called the radius of G.

Example The graph,

has radius 2 (the central vertex is shaded yellow).

Does every graph have a central vertex? Is it possible for a graph to have more than one central vertex? Give examples or arguments to support your conclusions.

Can you think if any examples of graphs in which every vertex is a central vertex?

The Minimal Connector Problem

Suppose some real-life situation is modeled by a graph G with weights assigned to its edges. By 'weights' we mean that there is a weight function,

,

and for each edge, e, the weight, w(e) usually represents some sort of cost (or profit) for using that edge.

Example A possible pictorial representation of a graph with weights is shown below.

The weights could represent:

Return to the starting point (the post office).

This problem may be reformulated in terms of weighted graphs, where the graph corresponds to the network of roads, and the weight of each edge corresponds to the length of the road represented by that edge.

The requirement is to find a closed walk that includes every edge at least once, and has the least possible weight.

Example The Traveling Sales Representative's Problem. The sales representative

has to visit several different cities, then return to the starting point, and,

travel the least possible distance.

This can also be reformulated in terms of weighted graphs. In this case, the requirement is to find a Hamiltonian cycle of least possible weight in a complete graph with weights.

Often, you want to find a connected subgraph of a graph G that uses every vertex of G (e.g. so you can go from any vertex to any other vertex in the subgraph) but so that the sum of the weights of all the edges in the subgraph is as small as possible. This is called the Minimal Connector Problem.

The solutions to this problem is given by Kruskal's Algorithm.

This is an algorithm for finding a minimum weight spanning tree in a connected graph G that has weights assigned to its edges - in particular, it solves the minimal connector problem for G.

Definition If T is any subgraph, define w(T) = sum of the weights of the edges of T. A minimum weight spanning tree is a spanning tree for which w(T) is as small as possible.

Kruskal's Algorithm

First choose any edge e₁ of smallest weight in G. Then choose edges e₂, e₃, . . . by choosing at each stage an edge (of smallest weight not already chosen) subject to the condition that it forms no circuit with any of the previous edges. If there are no such edges left, then what you have already chosen are the edges of a minimum weight spanning tree.

Example A cube graph with weights, and a minimum spanning tree. The weight of the minimum weight spanning tree is 34.

Proof (That Kruskal's Algorithm always works for a connected graph G.)

First, note that if e₁, e₂, . . . , e_m are the edges chosen by the time the algorithm finishes, then these edges must form a connected subgraph of G, that uses every vertex of G. (If not, then you would have a forest, not a tree, but G is connected so there will be some edges that could not be some edges that could be chosen as e_{m + 1}, etc.)

It is necessary to prove that T is a minimum weight spanning tree. Let S be any spanning tree for G (of minimum weight). Consider e₁ to e_m in turn. Choose the first one of these that isn't an edge of S, say e_k. Add e_k to S. This creates a circuit in S that has an edge e that can't be in T (as T has no circuits). By the choice of e_k , w(e_k)=< w(e). Remove e from S and replace it by e_k. This gives a new spanning tree S' with w(S') =<w(S). Continue in this way, choosing the next e_l that isn't in S', etc. Eventually you get:

.

So, w(T) = w(S). Since S is a minimal spanning tree, T is a minimal spanning tree, too. This completes the proof.

---

Back to MMS Main Page || Back to Graph Theory Contents Page