image Graph Theory Lessons image

rule

previous index next Lesson 32: Trees

A tree is a connected graph that has no circuits as subgraphs.

A graph that has no circuits as subgraphs but is not necessarily connected is a forest.


Java Web Start Activity:
In the Java Web Start application below you can draw examples of trees for yourself.


In many situations we will choose one of the vertices of a tree to be special and call it the root of the tree. The graph is then called a rooted tree. Usually rooted trees are drawn in a tree-like shape with the root at the top. A tree that is not a rooted tree is called a free tree.


Java Web Start Activity:
In the Java Web Start application below you can draw examples of rooted trees for yourself. By choosing different vertices to be the root you can make the application draw the tree differently.


In a rooted tree, the vertices adjacent to the root vertex are called its children. The children of the root are said to be on level 1. The root vertex is the parent vertex of the vertices on level 1. In the same way, if a vertex v is at level i, then the vertices other than the parent vertex of v that are adjacent to v are the children of v. The children of v are at level i+1 and v is their parent vertex. Note that the number of levels depends on which vertex is chosen to be the root. The number of levels is the height of the tree.

Vertices that have no children are called leaves. The vertices that are not leaves are said to be internal vertices. The root counts as an internal vertex.

If all the internal vertices of a tree have the same number, say n, of vertices then it is an n-ary tree. A n-ary tree with n=2 is called a binary tree. Figure 32.1 shows a binary tree with three levels. The leaves of the tree are vertices 8, 9, 5, 6, 10, 11.

A binary tree with 3 levels
Fig 32.1, A binary tree with 3 levels

If all the leaves of an n-ary tree are at the same level then it is a full n-ary tree.


Petersen Activity:
In the Petersen program select Graph | Named Graph | Full n-ary Tree. When asked for n, input 2 and when asked for the number of levels input 3. You should get a graph that looks like figure 32.2.

A full binary tree with 3 levels
Fig 32.2, A full binary tree with 3 levels


Java Web Start Activity:
The Java Web Start application below will give you more examples of full n-ary trees.


Questions:
  1. Use the Petersen program and, by looking at the statistics, find the number of vertices and the number of edges in a full binary tree with
    • 2 levels
    • 3 levels
    • 4 levels.
  2. Note that the number of vertices in a full binary tree with h levels is 1 + 2 + 22 + 23 + ... + 2h. What is the sum of this series?
  3. How many leaves does a full binary tree with h levels have? How many leaves does a full binary tree with 25 levels have?
  4. How many internal vertices does a full binary tree with h levels have?

An n-ary tree with n = 3 is called a ternary tree. Figure 32.1 shows a full ternary tree with 3 levels.

Fig 32.3, A full ternary tree with 3 levels


Questions:
  1. How many vertices will a full ternary tree with h levels have?
  2. How many leaves are there in
    • a full ternary tree with 25 levels?
    • a full n-ary tree with h levels?

  3. Note that in any rooted tree, every vertex has an edge joining it to its parent (except the root which has no parent). How many edges in total should a tree with n vertices have?
  4. Use the program to decide which of the trees in question 1) are bipartite.
  5. If a graph is a tree, what is its chromatic number.
  6. If an n x n matrix is the adjacency matrix of a tree, how many zeros and how many ones should it have?
  7. Prove that if a tree T1 is a subgraph of a tree T2 then T1 is an induced subgraph of T2.


© C. Mawata