Many of the applications of graph theory, particularly in computing, use a certain kind of tree, called a ‘rooted tree’. This is simply a tree where a particular vertex has been distinguished or singled out from the rest. These are the trees used to show the relationships between a person’s descendants—the familiar ‘family
tree’. The picture below is a typical family tree showing the descendants of greatgrandmother Mary who would be the distinguished vertex in this case.

Rooted trees are perhaps most familiar in computing as models for the structure of file directories. The next picture shows part of a typical multi-user file directory, organized as a rooted tree. Directories are organized in this way for two main reasons: so that related files can be grouped conveniently together and, in multiuser systems, to protect the security of the users’ files. Each user would usually have a password which would be required to gain access to his or her files.








A rooted tree is a pair (T, v∗) where T is a tree and v∗ ∈ VT. The distinguished vertex v∗ is called the root of the tree.
A leaf in a rooted tree is a vertex which has degree 1 which is not equal to the root; a decision vertex (or internal vertex) is a vertex which is neither the root nor a leaf.
The name ‘decision vertex’ comes from so-called ‘decision trees’. These arerooted trees which are used to model multi-stage decision processes where the decision made at one stage affects the possible decisions available at the next stage. The decision vertices represent the points at which decisions need to be made. Sometimes it is convenient to use slightly less formal terminology and refer to a ‘rooted tree T with root v∗’ rather than having always to use the ordered pair notation (T, v∗) for a rooted tree.
Let (T, v∗) be a rooted tree. The level of a vertex w of T is the length of
the (unique) path in T from v∗ to w. The height of T is the maximum of
the levels of its vertices.
Let T be a rooted tree and let p be a vertex of level k = 0. (This is just another
way of saying that p = v∗.) Since the path in T from v∗ to p is unique, it follows
that p is adjacent to a unique vertex of level k − 1. The terminology of the next
definition is motivated by the example of a family tree.