Definition:Arborescence/Definition 3

From ProofWiki
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$ 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$.


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:


Also defined as

Variants of the definitions can be found, as follows:


Also see

  • Results about arborescences can be found here.


Sources