Rooted trees
If you select an arbitrary vertex (called the root) in a tree, and turn
every (undirected) edge of the tree into an edge directed away from
the root, the resulting directed tree will be what is called a rooted tree.
- If (u,v) is an edge, u is called the parent of v and v is called a child
- If the vertices u and v have the same parent, they are called siblings.
- If there is a path from u to v (u?v), u is called an ancestor of v and
v is called a descendant of u.
- Vertices with children are called internal vertices, and those without
children are called leaves.
- If v is a vertex in the tree, the subtree of the tree with v as its root is
the subgraph of the tree consisting of v and its descendants and all
the edges incident to these descendants.