Arborescence (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.[1][2]

Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root. 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]

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

Furthermore, some authors define arborescence as to be a spanning directed tree of a given digraph.[9] The same can be said about some its synonyms, especially branching.[9] Other authors use branching to denote a forest of arborescences, with the latter notion defined in broader sense given at beginning of this article.[10]

See also[edit]

References[edit]

  1. ^ a b doi:10.1090/S0002-9939-1989-0967486-0
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  2. ^ a b Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9. 
  3. ^ 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. 
  4. ^ a b Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38. ISBN 1-4008-3535-6. 
  5. ^ 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. 
  6. ^ 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. 
  7. ^ David Makinson (2012). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 167-168. ISBN 978-1-4471-2499-3. 
  8. ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5. 
  9. ^ a b Jørgen Bang-Jensen; Gregory Z. Gutin (2008). Digraphs: Theory, Algorithms and Applications. Springer. p. 339. ISBN 978-1-84800-998-1. 
  10. ^ James Evans (1992). Optimization Algorithms for Networks and Graphs, Second Edition. CRC Press. p. 59. ISBN 978-0-8247-8602-1.