Graph Theory Lessons

Lesson 13: Trees

For this lesson you will need to use the geometric series. Consult your calculus books if you need to. A tree is a connected graph that has no circuits. In the program select 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 19

Fig. 19, A full binary tree with 3 levels.

In a full n-ary tree we have a special vertex in the tree called the root. The root has edges to n other vertices called its children. The children of the root are said to be on level 1. If we have h levels, then for 0 < i < h, each vertex on levelihas n children of its own which are on level i+1. The vertices on the last level, h, have no children and are called leaves. The vertices that are not leaves are said to be internal vertices. The root counts as an internal vertex. In figure 19 the root is vertex 1 and n=2. The internal vertices are vertices 1 through 7 and the leaves are vertices 8 through 15. When n is 2, as in our example, the tree is called a binary tree so figure 19 is a full binary tree with 3 levels . This tree has 8 leaves. Tha applet below will show you a few more full n-ary trees.

Full n-ary trees

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.
Note that the number of vertices in a full binary tree with h levels is 1+2+2²+2³+...+2^h. What is the sum of this series?
How many leaves does a full binary tree with h levels have? How many leaves does a full binary tree with 25 levels have?
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 20 shows a full ternary tree with 3 levels.

Fig. 20. A full ternary tree with 3 levels.
How many vertices will a full ternary tree with h levels have?
- How many leaves will a full ternary tree with 25 levels have?
- How many leaves will a full n-ary tree with h levels have?
Note that in any 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?
Use the program to decide which of the trees in question 1) are bipartite.
If a graph is a tree, what is its chromatic number?
If an n x n matrix is the adjacency matrix of a tree, how many zeros and how many ones should it have?
(Breadth First Traversal on next page...) e-mail: C. Mawata © C. Mawata