For faster navigation, this Iframe is preloading the Wikiwand page for Arborescence (graph theory).

Arborescence (graph theory)

In graph theory, an arborescence is a directed graph having a distinguished vertex u (called the root) such that, for 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] An arborescence is also 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.

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 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[16] or anti-arborescence.[17] 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". NetworkX 2.6.2 documentation. Retrieved 2021-12-10. arborescence - A directed tree with each node having, at most, one parent. So the maximum in-degree is equal to 1.
  2. ^ 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. ^ a b 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. ^ a b 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. ^ 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.
  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. ^ a b c Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4.
  13. ^ a b 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 (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0.
  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
{{bottomLinkPreText}} {{bottomLinkText}}
Arborescence (graph theory)
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?