Arborescence (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v.

Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.

See also[edit]

References[edit]