11.1 Introduction to trees Flashcards
Trees introduction:
A connected graph that contains no simple circuits is called a tree.
Trees can be used
to model procedures carried out using a sequence of decisions.
Definition 1:
Tree
A tree is a connected undirected graph with no simple circuits.
-Because a tree cannot have a simple circuit, a tree cannot contain multiple edges or loops. Therefore any tree must be a simple graph.
Forests :
graphs containing
no simple circuits that are not necessarily connected.
These graphs are called forests and have
the property that each of their connected components is a tree.
Thm 1 :
Alternative defition of tree:
prove it.
An undirected graph is a tree if and only if there is a unique simple path between any two of
its vertices.
Definition 2:
Rooted Tree:
and lil more info bout it.. generic.
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.
Note that
different choices of the root produce different rooted trees.
- Arrows can be omitted as the choice of root determines the direction and roots usually at top.
Rooted trees can also be defined recursively.
Refer to Section 5.3 to see how this can be done
Terminology for trees :
just mention dont define:
The terminology for trees has botanical and genealogical origins
- Parent
- Child
- Siblings.
- Ancestors
- Descendants
- leaf
- Internal vertices
Parent and child ?
Sibling :
If v is a vertex in T other than the root, the parent of v is the unique vertex u such that there
is a directed edge from u to v (the reader should show that such a vertex is unique). When u is
the parent of v, v is called a child of u
Vertices with the same parent are called siblings.
Ancestors and Descendants :
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 (that is, its parent, its parent’s parent, and so
on, until the root is reached). The descendants of a vertex v are those vertices that have v as
an ancestor.
leaf and internal vertices :
when is a root leaf ?
when is it internal vertex ?
A vertex of a rooted tree is called a leaf if it has no children. Vertices that have
children are called internal vertices. The root is an internal vertex unless it is the only vertex
in the graph, in which case it is a leaf.
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 and its descendants and all edges incident to these descendants.
Definition 3:
m-ary tree?
full m-ary tree ?
binary 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. An m-ary
tree with m = 2 is called a binary tree.
ORDERED ROOTED TREES :
An ordered rooted tree is a rooted tree where the children
of each internal vertex are ordered.
Ordered rooted trees are drawn so that the children of each
internal vertex are shown in order from left to right. Note that a representation of a rooted tree
in the conventional way determines an ordering for its edges. We will use such orderings of
edges in drawings without explicitly mentioning that we are considering a rooted tree to be
ordered.
About ordered binary tree :
In an ordered binary tree (usually called just a binary tree), if an internal vertex has two
children, the first child is called the left child and the second child is called the right child.
The tree rooted at the left child of a vertex is called the left subtree of this vertex, and the tree
rooted at the right child of a vertex is called the right subtree of the vertex.
Tree, number edges and vertices relation: connected graph too.
Because the graph is connected and the number of edges is one less than
the number of vertices, it must be a tree
Ex. 15
