arborescence (graph theory)

The term arborescence comes from French.{{cite book|author=Per Hage and Frank Harary|title=Island Networks: Communication, Kinship, and Classification Structures in Oceania|year=1996|publisher=Cambridge University Press|isbn=978-0-521-55232-5|page=43}} 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,{{cite book|author=Stanley Gill Williamson|title=Combinatorics for Computer Science|year=1985|publisher=Courier Dover Publications|isbn=978-0-486-42076-9|page=288}}{{cite book|author1=Mehran Mesbahi|author2=Magnus Egerstedt|title=Graph Theoretic Methods in Multiagent Networks|year=2010|publisher=Princeton University Press|isbn=978-1-4008-3535-5|page=38}} out-arborescence,{{cite book|author1=Ding-Zhu Du|author2=Ker-I Ko|author3=Xiaodong Hu|title=Design and Analysis of Approximation Algorithms|year=2011|publisher=Springer Science & Business Media|isbn=978-1-4614-1701-9|page=108}} out-tree, and even branching being used to denote the same concept.{{cite book|author1=Jonathan L. Gross|author2=Jay Yellen|author3=Ping Zhang|author3-link=Ping Zhang (graph theorist)|title=Handbook of Graph Theory, Second Edition|year=2013|publisher=CRC Press|isbn=978-1-4398-8018-0|page=116}} Rooted tree itself has been defined by some authors as a directed graph.{{cite book|author=David Makinson|author-link=David Makinson|title=Sets, Logic and Maths for Computing|year=2012|publisher=Springer Science & Business Media|isbn=978-1-4471-2499-3|pages=167–168}}{{cite book|author=Kenneth Rosen|title=Discrete Mathematics and Its Applications, 7th edition|year=2011|publisher=McGraw-Hill Science|page=747|isbn=978-0-07-338309-5}}

Furthermore, some authors define an arborescence to be a spanning directed tree of a given digraph.{{cite book|author=Alexander Schrijver|title=Combinatorial Optimization: Polyhedra and Efficiency|year=2003|publisher=Springer|isbn=3-540-44389-4|page=34}} The same can be said about some of its synonyms, especially branching.{{cite book|author1=Jørgen Bang-Jensen|author2=Gregory Z. Gutin|title=Digraphs: Theory, Algorithms and Applications|year=2008|publisher=Springer|isbn=978-1-84800-998-1|page=339}} Other authors use branching to denote a forest of arborescences, with the latter notion defined in broader sense given at beginning of this article,{{cite book|author=James Evans|title=Optimization Algorithms for Networks and Graphs, Second Edition|year=1992|publisher=CRC Press|isbn=978-0-8247-8602-1|page=59}}{{cite book|author1=Bernhard Korte|authorlink1=Bernhard Korte|author2=Jens Vygen|title=Combinatorial Optimization: Theory and Algorithms|year=2012|publisher=Springer Science & Business Media|isbn=978-3-642-24488-9|page=18|edition=5th}} 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{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox|date=2008|publisher=Springer Science & Business Media|isbn=978-3-540-77978-0|pages=52 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf}} or anti-arborescence.{{cite book|author1=Bernhard Korte|authorlink1=Bernhard Korte|author2=Jens Vygen|title=Combinatorial Optimization: Theory and Algorithms|year=2012|publisher=Springer Science & Business Media|isbn=978-3-642-24488-9|page=28|edition=5th}} W. T. Tutte distinguishes between the two cases by using the phrases arborescence diverging from [some root] and arborescence converging to [some root].{{citation|last1=Tutte|first1=W.T.|title=Graph Theory|publisher=Cambridge University Press|year=2001|isbn=978-0-521-79489-3|pages=126–127}}

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, ... {{OEIS|A000081}}.

• Edmonds' algorithm
• Multitree

{{Reflist}}

• {{mathworld|title=Arborescence|urlname=Arborescence}}
• {{mathworld|title=Rooted Tree|urlname=RootedTree}}

{{DEFAULTSORT:Arborescence (Graph Theory)}}

Category:Trees (graph theory)

Category:Directed acyclic graphs