Discrete Mathematical Structures by Pearson

Trees 11-3

11.1.3 Directed and Undirected Trees

Mathematically, a treeT can be defined as T = (V, E) where V = {v

0

, v

1

, v

2

,…, v

n

} is a set of

vertices (or notes) and E = {e

1

, e

2

, e

3

,…, e

k

} is a set of edges if there is a vertex v

0

in V with the

property that there exists a path from v

0

to every other vertex in V. The vertex v

0

is called the root

of the tree. The tree T is called rooted tree and can be denoted by (T, v

0

).

The vertex v

0

has in-degree zero, whereas every other vertex of V has in-degree one. A tree

may be directed or undirected. The graph in Fig. 11.2 are undirected trees.

Directed Tree: A directed tree is an acyclic directed graph ...