Definition:Arborescence/Definition 2
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:
- $(1): \quad$ $G$ is an orientation of a tree
- $(2): \quad$ For each $v \in V$, $v$ is reachable from $r$.
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
- May 2009: Kristóf Bérczi and András Frank: Packing Arborescences (Egerváry Research Group Ser. Technical Report no. TR-2009-04): $\S 1$