Arborescence (graph theory)
Encyclopedia
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, an arborescence is a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
in which all edges point away from the root. Every arborescence is a directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
(DAG), but not every DAG is an arborescence.