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 level i
has 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.
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+22+23+...+2h. 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 an n x n matrix is the adjacency matrix of a tree, how many zeros and how
many ones should it have?
Recall (see your textbook if necessary) that in a depth first search we go to the next level at the
earliest opportunity while in a breadth first search we search all the vertices at a given level before
going to the next level. Get the graph in figure 19 again and choose
Find then Search and Depth First. When asked which vertex to find
input 11. You will see the edges used in a depth first search appear first in green , then in red etc. You
can use the buttons at the bottom left corner to speed up or slow down the graphics. Do the same for a
breadth first search.
Make a table with three columns labeled "Vertex", "Depth First" and "Breadth First" and for
each vertex in the graph of figure 19 find how many steps it takes to find it using the two search
methods.
Which vertices in this graph (fig. 19) require the same number of steps when you do a breadth
first search as when you do a depth first search?
By adding up the entries in the columns and dividing by 15, find the average number of steps
needed for
a depth first search
a breadth first search
What is the the average number of steps needed to search a tree with n vertices using either method?
Suppose you have a full ternary tree with 25 levels (don't even think of drawing it)
and vertices labeled left to right like in figure 20.
What level is vertex 50 in?
What are the labels of the three children of vertex 50?
Graph Theory Lessons
Lesson 13: Trees
