In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, an arborescence is a
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
in which, for a
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
(called the ''root'') and any other vertex , there is exactly one
directed path
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes c ...
from to .
An arborescence is thus the directed-graph form of a
rooted tree
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...
, understood here as an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
.
Equivalently, an arborescence is a directed, rooted
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
in which all edges point away from the root; a number of other equivalent characterizations exist.
Every arborescence is a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
(DAG), but not every DAG is an arborescence.
An arborescence can equivalently be defined as a
rooted digraph in which the path from the root to any other vertex is unique.
Definition
The term ''arborescence'' comes from French.
Some authors object to it on grounds that it is cumbersome to spell.
There is a large number of synonyms for arborescence in graph theory, including directed rooted tree
out-arborescence,
out-tree,
and even branching being used to denote the same concept.
''Rooted tree'' itself has been defined by some authors as a directed graph.
Further Definitions
Furthermore, some authors define an arborescence to be a spanning directed tree of a given digraph.
The same can be said about some of its synonyms, especially ''branching''.
Other authors use ''branching'' to denote a forest of arborescences, with the latter notion defined in broader sense given at beginning of this article,
but a variation with both notions of the spanning flavor is also encountered.
It's also possible to define a useful notion by reversing all the arcs of an arborescence, i.e. making them all point to the root rather than away from it. Such digraphs are also designated by a variety of terms such as in-tree
or anti-arborescence
etc.
W. T. Tutte
William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
distinguishes between the two cases by using the phrases ''arborescence diverging from''
ome rootand ''arborescence converging to''
ome root
The number of rooted trees (or arborescences) with ''n'' nodes is given by the sequence:
: 0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, ... .
See also
*
Edmonds' algorithm
*
Multitree
In combinatorics and Order theory, order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two Vertex (graph theory), vert ...
References
External links
*
*
Trees (graph theory)
Directed acyclic graphs
{{combin-stub