# Definition:Arborescence

## Contents

## Definition

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

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

### Root of Arborescence

The vertex $r$ of $G$ is known as the **root of (the arborescence) $G$**.

## Equivalence of Definitions

These definitions are shown to be equivalent in Equivalence of Definitions of Arborescence.

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