1 of 16

3.1 TREES

3.1 TREES

1

2 of 16

Trees

  • Let A be a set and let T be a relation on A.
  • We say that T is a tree

if there is a vertex vo in A with the property that there exists a unique path in T from vo to every other vertex in A, but no path from vo to vo.

3.1 TREES

2

3 of 16

Trees

  • vo is called root of the tree T and T is then referred to as a rooted tree.
  • If (T, vo) is a rooted tree on the set A, an element v of A will often be referred to as a vertex in T.

3.1 TREES

3

4 of 16

Trees

  • Theorem 1

Let (T, vo) be a rooted tree. Then

      • There are no cycles in T
      • vo is the only root of T
      • Each vertex in T, other then vo has in-degree one, and vo has in-degree zero.

3.1 TREES

4

5 of 16

Trees

  • The digraph of the tree from Theorem 1 can be described as below

​

3.1 TREES

5

6 of 16

Trees

  • Explanations from the diagraph
    • vo is a parent of these level 1 vertices
    • The level 1 vertices are called offspring of vo
    • Example:
      • vo is called the parent of the three offspring v7, v8 and v9
      • The offspring of any one vertex are sometimes called siblings.
      • The largest level number of a tree is called the height of the tree.
      • The vertices of the tree that have no offspring are called the leaves of the tree.
      • If a vertex has four offspring, for example, we automatically assume that they are ordered by arranging them from left to right. If ordering is needed we say an ordered tree.

3.1 TREES

6

7 of 16

Trees

  • Theorem 2

Let (T, vo) be a rooted tree on a set A. Then

      • T is irreflexive
      • T is asymmetric
      • If (a,b) ∈ T and (b,c) ∈ T, then (a,c) ∉ T, for all a, b, and c in A.

​

3.1 TREES

7

8 of 16

Trees

  • Example 1
    • Let A = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10} and let

T = {(v2, v3), (v2, v1), (v4, v5), (v4, v6), (v5, v8), (v6, v7), (v4, v2), (v7, v9), (v7, v10)}.

​

Show that T is a rooted tree and identify the root

3.1 TREES

8

9 of 16

Trees

3.1 TREES

9

10 of 16

Trees

  • From Example 1
    • If n is a positive integer, a tree T is an n-tree if every vertex has at most n offspring.
    • If all vertices of T, other than the leaves, have exactly n offspring, T is an complete n-tree.
    • A two-tree is often called a binary tree.
    • A complete two-tree is often called a complete binary tree.
    • Descendants of the vertex v refer to all vertices of T that can be reached by a path beginning at v.

​

​

3.1 TREES

10

11 of 16

Trees

  • Theorem 3

If (T, vo) is a rooted tree and v ∈ T, then T(v) is also a rooted tree with root v. T(v) is the subtree of T beginning at v.

​

3.1 TREES

11

12 of 16

Trees

  • Example
    • Consider the tree of Example 1. This tree has root v4 and among the subtrees of T are T(v5), T(v2) and T(v6) and even T(v7)
    • We can draw them.

3.1 TREES

12

13 of 16

Trees

  • Answer

​

3.1 TREES

13

14 of 16

Trees

  • Exercise
    • In Exercise 1-3, each relation R is defined on the set A. In each case determine if R is a tree and if it is, find the root.
      1. A = {a, b, c, d, e}, R = {(a, d), (b, c), (c, a), (d, e)}.
      2. A = {1, 2, 3, 4, 5, 6}, R = {(1, 1), (2, 1), (2, 3), (3,4), (4, 5), (4, 6)}
      3. A = {t, u, v, w, x, y, z}, R = {(t, u), (u, w), (u, x), (u, v), (v, z), (v, y)}

​

3.1 TREES

14

15 of 16

Trees

  • Exercise
    • Consider the rooted tree (T, vo) below

3.1 TREES

15

16 of 16

Trees

  1. List all level 3 vertices
  2. List all leaves
  3. What are the sibling of v8
  4. What are the descendants of v8
  5. Compute the tree T(v2)
  6. Compute the tree T(v3)
  7. What is the height of (T, vo)
  8. What is the height of (T, v3)
  9. Is (T, vo) an n-tree? If so, for what integer n?
  10. Is (T, vo) a complete n-tree? If so, for what integer n?

3.1 TREES

16