Scribd
Upload
82 views

Discrete Math Introduction

1. A rooted tree is a tree with a designated root node that branches out and defines parent-child relationships between nodes. 2. Key terms for rooted trees include parent, child, siblings, ancestors, descendants, leaves, internal vertices, and subtrees. 3. Rooted trees can be n-ary if each internal node has no more than n children, or full n-ary if each has exactly n children. A binary tree is a type of 2-ary tree.

Uploaded by

Nur Firdaus
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
82 views

Discrete Math Introduction

1. A rooted tree is a tree with a designated root node that branches out and defines parent-child relationships between nodes. 2. Key terms for rooted trees include parent, child, siblings, ancestors, descendants, leaves, internal vertices, and subtrees. 3. Rooted trees can be n-ary if each internal node has no more than n children, or full n-ary if each has exactly n children. A binary tree is a type of 2-ary tree.

Uploaded by

Nur Firdaus
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Introduction

A rooted tree is a tree in which a special ("labeled") node is singled out. This node is called the
"root" or (less commonly) "eve" of the tree. Rooted trees are equivalent to oriented trees (Knuth
1997, pp. 385-399). A tree which is not rooted is sometimes called a free tree, although the
unqualified term "tree" generally refers to a free tree.

A rooted tree in which the root vertex has vertex degree 1 is known as a planted tree.

A rooted tree GG is a connected acyclic graph with a special node that is called the root of the tree
and every edge directly or indirectly originates from the root. An ordered rooted tree is a rooted
tree where the children of each internal vertex are ordered. If every internal vertex of a rooted tree
has not more than m children, it is called an m-ary tree. If every internal vertex of a rooted tree has
exactly m children, it is called a full m-ary tree. If m=2m=2, the rooted tree is called a binary tree.

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
unique vertex 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
and its descendants and all edges incident to these descendants.

Some Important Terms for Rooted Trees:

1. If the starting path is (a, b) in a rooted tree, a is called the parent of b.


2. If a has children, then a is internal node
3. If a has no children, then b is a leaf.
4. a and b are siblings if they have same parent.
5. The height of a tree is measured as the length of the longest possible path from its root to
any vertex.
6. The level of a vertex is known as the path length from its starting point or the root. The root
is starts from the point 0.
7. Here, a the starting point is known as an ancestor of b.
8. Here, b is known as a descendent of a. Note that here, a is an ancestor.n-ary Trees:
A rooted tree is called as n-ary tree if every vertex has no more than n children. It is called as full
if each internal vertex that is non leaf has exactly n children. A binary tree is any example of a 2
ary tree. These are very useful for taking decisions of yes or no problems.

In other words, a rooted tree is an n-ary tree if and only if every internal vertex has less than
equal to n children. If every internal vertex are found to having exactly m children then it is
considered as a full n-ary tree.
Problem Statement
i) What is the function of rooted tree in our daily life ?

ii) How rooted tree was established ?

iii) How to uses rooted tree ?

iv) What is characteristics of rooted tree ?

v) What is the edges of rooted tree ?

vi) What is the decomposition of rooted tree ?

vii) What is the different between rooted tree and unrooted tree ?

viii) What is the main objective using rooted tree ?

You might also like