HOME

TheInfoList



OR:

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 conn ...
, 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 position ...
(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 '' ...
, 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 ar ...
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 v ...
(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 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-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 vertices, or equivalently in which the ...


References


External links

* * Trees (graph theory) Directed acyclic graphs {{combin-stub