Arborescence (graph theory)
||It has been suggested that this article be merged into Tree (graph theory). (Discuss) Proposed since July 2014.|
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 defined as an undirected graph.
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.
Furthermore, some authors define arborescence as to be a spanning directed tree of a given digraph. The same can be said about some 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.
- Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9.
- 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.
- 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.
- 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. p. 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.
- 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.
|This combinatorics-related article is a stub. You can help Wikipedia by expanding it.|