Graph Theory: Trees and Matrices

Which of the following graphs is guaranteed to be a tree?

What is the minimum number of edges required in a tree with 10 vertices?

What is the root of a rooted tree?

What is the number of vertices in a full 3-ary tree with 2 internal vertices?

Which of the following is a characteristic of a tree?

What is the term for the vertices below a vertex in a rooted tree?

What is the term for the vertex directly above a vertex in a rooted tree?

What is the number of internal vertices in a full m-ary tree with n vertices?

How many edges are required in a full binary tree with 8 vertices?

In a full m-ary tree with n vertices, what is the number of leaves?

What is the height of a rooted tree?

A rooted m-ary tree of height h is balanced if...

In a universal address system, how are the vertices labeled?

What is the maximum number of leaves in an m-ary tree of height h?

What is the level of the root in a rooted tree?

How can we totally order the vertices in a universal address system?

Introduction to Trees

A tree is a connected undirected graph with no simple circuits.
An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.
A tree with m-vertices has m-1 edges.

Rooted Trees

A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.
Terminologies in rooted trees include ancestors, parent, descendants, children, and siblings.

Properties of Trees

A tree with n nodes has n-1 edges (Theorem 2).
A full m-ary tree with i internal vertices contains n = mi + 1 vertices (Theorem 3).
A full m-ary tree with n vertices contains (n-1)/m internal vertices and ((m-1) n+1)/m leaves (Corollary).
A full m-ary tree with:
- 1. n vertices has i = (n-1)/m internal vertices and l = [(m-1)n+1]/m leaves (Theorem 4).
- 1. i internal vertices has n = mi + 1 vertices and l = (m-1)i + 1 leaves (Theorem 4).
- 1. l leaves has n = (ml-1)/(m-1) vertices and i = (l-1)/(m-1) internal vertices (Theorem 4).

Properties of Rooted Trees

The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex.
The height of a rooted tree is the maximum of the levels of vertices.
A rooted m-ary tree of height h is balanced if all leaves are at levels h or h-1.
There are at most mh leaves in an m-ary tree of height h.

Tree Traversal

Universal Address Systems are used to label vertices in a tree.
Tree traversal can be done using the lexicographic ordering of vertex labels in the universal address system.

Learn about the basics of tree graphs, including subtrees and matrices representation. Understand the definition and theorem of a tree in graph theory.