Arborescence (graph theory)

From HandWiki
Short description: Directed graph where every node has exactly one path to it from the root

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

Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist.[4][5] 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.[2]

Definition

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

Further Definitions

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

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

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, ... (sequence A000081 in the OEIS).

See also

References

  1. "Tree". https://networkx.org/documentation/stable/reference/algorithms/tree.html. "arborescence - A directed tree with each node having, at most, one parent. So the maximum in-degree is equal to 1." 
  2. 2.0 2.1 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. 
  3. 3.0 3.1 Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9. 
  4. Jean-Claude Fournier (2013). Graphs Theory and Applications: With Exercises and Problems. John Wiley & Sons. pp. 94–95. ISBN 978-1-84821-070-7. 
  5. Jean Gallier (2011). Discrete Mathematics. Springer Science & Business Media. pp. 193–194. ISBN 978-1-4419-8046-5. 
  6. 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. 
  7. 7.0 7.1 Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38. ISBN 1-4008-3535-6. 
  8. 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. 
  9. 9.0 9.1 Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 116. ISBN 978-1-4398-8018-0. 
  10. David Makinson (2012). Sets, Logic and Maths for Computing. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3. 
  11. Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5. 
  12. 12.0 12.1 12.2 Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4. 
  13. 13.0 13.1 Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Digraphs: Theory, Algorithms and Applications. Springer. p. 339. ISBN 978-1-84800-998-1. 
  14. James Evans (1992). Optimization Algorithms for Networks and Graphs, Second Edition. CRC Press. p. 59. ISBN 978-0-8247-8602-1. 
  15. Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 18. ISBN 978-3-642-24488-9. 
  16. Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox. Springer Science & Business Media. pp. 52. ISBN 978-3-540-77978-0. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf. 
  17. Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9. 
  18. Tutte, W.T. (2001), Graph Theory, Cambridge University Press, pp. 126–127, ISBN 978-0-521-79489-3 

External links