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.
- ^ "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.
- ^ 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.
- ^ Cite error: The named reference
Williamson1985was invoked but never defined (see the help page). - ^ Jean-Claude Fournier (2013). Graphs Theory and Applications: With Exercises and Problems. John Wiley & Sons. pp. 94–95. ISBN 978-1-84821-070-7.
- ^ Jean Gallier (2011). Discrete Mathematics. Springer Science & Business Media. pp. 193–194. ISBN 978-1-4419-8046-5.
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search