Category:Definitions/Arborescences
Jump to navigation
Jump to search
This category contains definitions related to Arborescences.
Related results can be found in Category:Arborescences.
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$.
Pages in category "Definitions/Arborescences"
The following 9 pages are in this category, out of 9 total.