Arborescence (graph theory) on:
[Wikipedia]
[Google]
[Amazon]
In
In graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, an arborescence is a directed graph where there exists a vertex (called the ''root'') such that, for any other vertex , there is exactly one directed walk from to (noting that the root is unique). 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 path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equi ...
, understood here as an undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
. An arborescence is also 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, e.g., including only woody plants with secondary growth, only ...
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 ...
(DAG), but not every DAG is an arborescence.
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 edges of an arborescence, i.e. making them all point in the direction of the root rather than away from it. Such digraphs are also designated by a variety of terms, such as in-tree or anti-arborescence. 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 theory, 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 subgraph reachabl ...
References
External links
* * {{DEFAULTSORT:Arborescence (Graph Theory) Trees (graph theory) Directed acyclic graphs