Definition:Arborescence
Definition
Let $G = \struct {V, A}$ be a digraph.
Let $r \in V$.
Definition 1
$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$.
Definition 2
$G$ is an arborescence of root $r$ if and only if:
- $(1): \quad$ $G$ is an orientation of a tree
- $(2): \quad$ For each $v \in V$, $v$ is reachable from $r$.
Definition 3
$G$ is an arborescence of root $r$ if and only if:
- $(1): \quad$ Each vertex $v \ne r$ is the final vertex of exactly one arc
- $(2): \quad$ $r$ is not the final vertex of any arc
- $(3): \quad$ For each $v \in V$ such that $v \ne r$ there is a directed walk from $r$ to $v$.
Definition 4
$G$ is an arborescence of root $r$ if and only if:
- $(1): \quad$ Each vertex $v \ne r$ has exactly one predecessor
- $(2): \quad$ $r$ has no predecessors
- $(3): \quad$ For each $v \in V$ such that $v \ne r$ there is a path 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.
Examples
English Sentence
The parsing structure of a sentence in English can be presented as an arborescence in the following format:
- $\begin {xy} \xymatrix@L + 2mu@ + 1em {
& & & \meta {sentence} \ar[dl] \ar[dr] \\ & & \meta {subject} \ar[d] & & \meta {predicate} \ar[dr] \\ & & \meta {noun \ phrase} \ar[dl] \ar[d] & & & \meta {verb \ phrase} \ar[dl] \ar[d] \\ & \meta {adjective} \ar[dl] & \meta {noun \ phrase} \ar[dl] \ar[d] & & \meta {verb} \ar[dl] & \meta {adverbial \ phrase} \ar[dl] \ar[d] \\ \mathtt {the} & \meta {adjective} \ar[dl] & \meta {noun \ phrase} \ar[dl] \ar[d] & \mathtt {jumps} & \meta {preposition} \ar[dl] & \meta {noun \ phrase} \ar[dl] \ar[d] \\ \mathtt {quick} & \meta {adjective} \ar[d] & \meta {noun \ phrase} \ar[d] & \mathtt {over} & \meta {adjective} \ar[dl] & \meta {noun \ phrase} \ar[dl] \ar[d]\\ & \mathtt {brown} & \meta {noun} \ar[d] & \mathtt {the} & \meta {adjective} \ar[d] & \meta {noun \ phrase} \ar[d]\\ & & \mathtt {fox} & & \mathtt {lazy} & \meta {noun} \ar[d] \\ & & & & & \mathtt {dog} } \end {xy}$
Also see
- Results about arborescences can be found here.