# Arborescence (graph theory)

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*. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph.^{[1]}^{[2]}

Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist.^{[3]}^{[4]} Every arborescence is a directed acyclic graph (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.^{[1]}

## DefinitionEdit

The term *arborescence* comes from French.^{[5]} Some authors object to it on grounds that it is cumbersome to spell.^{[6]} There is a large number of synonyms for arborescence in graph theory, including **directed rooted tree**^{[2]}^{[6]} **out-arborescence**,^{[7]} **out-tree**,^{[8]} and even **branching** being used to denote the same concept.^{[8]} *Rooted tree* itself has been defined by some authors as a directed graph.^{[9]}^{[10]}^{[11]}

### Further DefinitionsEdit

Furthermore, some authors define an arborescence to be a spanning directed tree of a given digraph.^{[11]}^{[12]} The same can be said about some of its synonyms, especially *branching*.^{[12]} Other authors use *branching* to denote a forest of arborescences, with the latter notion defined in broader sense given at beginning of this article,^{[13]}^{[14]} but a variation with both notions of the spanning flavor is also encountered.^{[11]}

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**^{[15]} or **anti-arborescence**^{[16]} etc. W. T. Tutte distinguishes between the two cases by using the phrases *arborescence diverging from* [some root] and *arborescence converging to* [some root].^{[17]}

The number of rooted trees (or arborescences) with *n* nodes is given by the sequence:

## See alsoEdit

## ReferencesEdit

- ^
^{a}^{b}Gordon, Gary (1989). "A greedoid polynomial which distinguishes rooted arborescences".*Proceedings of the American Mathematical Society*.**107**(2): 287. doi:10.1090/S0002-9939-1989-0967486-0. - ^
^{a}^{b}Stanley Gill Williamson (1985).*Combinatorics for Computer Science*. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9. **^**Jean-Claude Fournier (2013).*Graphs Theory and Applications: With Exercises and Problems*. John Wiley & Sons. pp. 94–95. ISBN 978-1-84821-070-7.**^**Jean Gallier (2011).*Discrete Mathematics*. Springer Science & Business Media. pp. 193–194. ISBN 978-1-4419-8046-5.**^**Per Hage and Frank Harary (1996).*Island Networks: Communication, Kinship, and Classification Structures in Oceania*. Cambridge University Press. p. 43. ISBN 978-0-521-55232-5.- ^
^{a}^{b}Mehran Mesbahi; Magnus Egerstedt (2010).*Graph Theoretic Methods in Multiagent Networks*. Princeton University Press. p. 38. ISBN 1-4008-3535-6. **^**Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011).*Design and Analysis of Approximation Algorithms*. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9.- ^
^{a}^{b}Jonathan L. Gross; Jay Yellen; Ping Zhang (2013).*Handbook of Graph Theory, Second Edition*. CRC Press. p. 116. ISBN 978-1-4398-8018-0. **^**David Makinson (2012).*Sets, Logic and Maths for Computing*. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3.**^**Kenneth Rosen (2011).*Discrete Mathematics and Its Applications, 7th edition*. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5.- ^
^{a}^{b}^{c}Alexander Schrijver (2003).*Combinatorial Optimization: Polyhedra and Efficiency*. Springer. p. 34. ISBN 3-540-44389-4. - ^
^{a}^{b}Jørgen Bang-Jensen; Gregory Z. Gutin (2008).*Digraphs: Theory, Algorithms and Applications*. Springer. p. 339. ISBN 978-1-84800-998-1. **^**James Evans (1992).*Optimization Algorithms for Networks and Graphs, Second Edition*. CRC Press. p. 59. ISBN 978-0-8247-8602-1.**^**Bernhard Korte; Jens Vygen (2012).*Combinatorial Optimization: Theory and Algorithms*(5th ed.). Springer Science & Business Media. p. 18. ISBN 978-3-642-24488-9.**^**Kurt Mehlhorn; Peter Sanders (2008).*Algorithms and Data Structures: The Basic Toolbox*(PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0.**^**Bernhard Korte; Jens Vygen (2012).*Combinatorial Optimization: Theory and Algorithms*(5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9.**^**Tutte, W.T. (2001),*Graph Theory*, Cambridge University Press, pp. 126–127, ISBN 978-0-521-79489-3

## External linksEdit

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |