---
tag: FT0SRH8HZD
kind: concept
name: Arborescence (graph theory)
aliases: [arboreal-decomposition, directed-rooted-tree, rooted-directed-tree]
sources:
  - wikipedia: en:13251077@r1369107778
    locator: Arborescence (graph theory)
    note: adopted
    mention: wikipedia://en/13251077
    sections: [Summary]
same_as:
  wikidata: Q1520825
  wikipedia: Arborescence (graph theory)
inventory: [F10P5CYGAM]
---

## Summary

In graph theory, an **arborescence** is a [[directed graph|0KFYGSHHF5]] where there exists a vertex $r$ (called the *root*) such that, for any other vertex $v$, there is exactly one [[directed walk|03NAMV1DHJ]] from $r$ to $v$ (noting that the root $r$ is unique). An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. An arborescence is also a directed rooted [[tree|062D9KXJB1]] in which all edges point away from the root; a number of other equivalent characterizations exist.