Category:Arborescences

From ProofWiki
Jump to navigation Jump to search

This category contains results about Arborescences.
Definitions specific to this category can be found in Definitions/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$.

Subcategories

This category has only the following subcategory.

Pages in category "Arborescences"

This category contains only the following page.