Definition:Arborescence/Definition 1
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, A}$ be a digraph.
Let $r \in V$.
$G$ is an arborescence of root $r$ if and only if:
- For each $v \in V$ there is exactly one directed walk from $r$ to $v$.
Root of Arborescence
The distinguished vertex $r$ of $G$ is known as the root of (the arborescence) $G$.
Also known as
An arborescence of root $r$ can be referred to as an an $r$-arborescence, or just an arborescence.
Various sources use different terms, for example:
- Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms calls an arborescence an oriented tree
- John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation calls an arborescence an ordered, directed tree.
Also defined as
Variants of the definitions can be found, as follows:
- Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms defines an arborescence of root $r$ so as to reverse the orientation of $G$, so that the arcs are all directed toward the root rather than away from it.
- John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation specifies that the successors of each vertex to be ordered "from the left", without specifying exactly what that means.
Also see
- Results about arborescences can be found here.
Sources
- Weisstein, Eric W. "Arborescence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Arborescence.html