16 Questions
Which of the following graphs is guaranteed to be a tree?
A connected graph with 7 vertices and 6 edges
What is the minimum number of edges required in a tree with 10 vertices?
9
What is the root of a rooted tree?
A vertex designated as the root
What is the number of vertices in a full 3-ary tree with 2 internal vertices?
7
Which of the following is a characteristic of a tree?
It has a unique simple path between any two vertices
What is the term for the vertices below a vertex in a rooted tree?
Descendants
What is the term for the vertex directly above a vertex in a rooted tree?
Parent
What is the number of internal vertices in a full m-ary tree with n vertices?
(n-1)/m
How many edges are required in a full binary tree with 8 vertices?
7
In a full m-ary tree with n vertices, what is the number of leaves?
((m-1)n+1)/m
What is the height of a rooted tree?
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
In a universal address system, how are the vertices labeled?
Starting from the root with 0, and labeling children from left to right
What is the maximum number of leaves in an m-ary tree of height h?
mh
What is the level of the root in a rooted tree?
0
How can we totally order the vertices in a universal address system?
Using lexicographic ordering of vertex labels
Study Notes
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:
-
- n vertices has i = (n-1)/m internal vertices and l = [(m-1)n+1]/m leaves (Theorem 4).
-
- i internal vertices has n = mi + 1 vertices and l = (m-1)i + 1 leaves (Theorem 4).
-
- 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.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
