Definition:Arborescence/Definition 2

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G = \left({V, A}\right)$ be a directed graph.

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 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.

Some sources, for example Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms, call an arborescence an oriented tree.


Also defined as

Some sources, for example Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms, define 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.


Also see

  • Results about arborescences can be found here.

Sources