11.1 Trees Flashcards
Definition of a Tree graph
A tree is an undirected graph with no simple circuits
Definition of a Forest
A (not-necessarily-connected) undirected graph without simple circuits is called a forest.
Rooted Trees
A rooted tree is a tree in which one vertex has been designated as the root and every edge is directedaway from the root.
Parent
Suppose that T is a rooted tree. If v is a vertex in T other than the root, the parent of v is the uniquevertex u such that there is a directed edge from u to v.
Child
If u is the parent of v, then v is called a child of u.
Siblings
Vertices with the same parent are called siblings.
Ancestors
The ancestors of a vertex other than the root are the vertices in the path from the root to this vertex,excluding the vertex itself and including the root.
Descendants
The descendants of a vertex v are those vertices that have v as an ancestor.
Leaf
A vertex of a tree is called a leaf if it has no children.
Internal Vertices
Vertices that have children are called internal vertices.
Subtree
If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting of a andits descendants and all edges incident to these descendants.
m-ary Tree
A rooted tree is called an m-ary tree if every internal vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children.
Binary Tree
An m-ary tree with m = 2 is called a binary tree.
Ordered Root Tree
An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered
Left and Right Child
In an ordered binary tree, the first child is called the left child and the second child is called theright child
Left and Right Subtree
The tree rooted at the left child is called the left subtree and the tree rooted at the right child iscalled the right subtree
How many edges in trees if have vertices? (Theorem 2)
A tree with n vertices has n − 1 edges.
How many vertices in tree if have internal vertices? (Theorem 3)
A full m-ary tree with i internal vertices contains n = mi + 1 vertices.
If only have vertices (Theorem 4)
- n vertices has i = n − 1/ m internal vertices andL = (m − 1)n + 1 / m leaves.
if only have internal vertices (Theorem 4)
i internal vertices has n = mi + 1 vertices andL = (m − 1)i + 1 leaves.
if only have leaves (Theorem 4)
L leaves has n = mL − 1 / m − 1 vertices andi = L − 1 / m − 1internal vertices
