Rooted tree

Dependencies:

1. Path in Graph

A directed graph $G$ is a rooted tree iff there is a vertex $r$, called the root, such that there is a unique simple path from $r$ to every vertex in $G$.

The root has in-degree 0. Every other vertex has in-degree 1, otherwise there would be multiple paths to it from the root. Therefore, we can also represent a rooted tree as a function $\operatorname{parent}: V \mapsto V \cup \{\textrm{null}\}$ where $\operatorname{parent}(r) = \textrm{null}$ and $\operatorname{parent}(v) = u$ iff $(u, v) \in T$.

Terminology

Let $T$ be a rooted tree.

• If there is an edge $(u, v)$ in $T$, then $v$ is a child of $u$ and $u$ is the parent of $v$.
• If there is a path of positive length from $u$ to $v$ in $T$, then $v$ is a descendant of $u$ and $u$ is an ancestor of $v$.
• A vertex with out-degree 0 is called a leaf. A vertex that is not a leaf is called an internal vertex.
• If 2 vertices have the same parent, they are called siblings.
• The subgraph of $T$ containing $v$ and all its descendants is a tree rooted at $v$. This is called the subtree of $T$ rooted at $v$.
• For a vertex $v$, let the length of the path from the root be $k$. Then the depth of $v$ is $k$.
• The height of a vertex is the length of the longest path from it to a leaf. The height of a rooted tree is the height of its root.

Dependency for:

1. Acyclic predecessor graph is union of rooted trees
2. The undirected version of a rooted tree is a free tree
3. Properties of DFS
4. Edge relaxations: Predecessor subgraph is a rooted tree
5. Shortest-path tree

Info:

• Depth: 2
• Number of transitive dependencies: 5

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph