Arborescence (graph theory)

Summary

In graph theory, an arborescence is a directed graph where there exists a vertex $r$ (called the root) such that, for any other vertex $v$, there is exactly one directed walk 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 in which all edges point away from the root; a number of other equivalent characterizations exist.