Arborescence (graph theory)
From Wikipedia, the free encyclopedia
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (June 2008) |
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.
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.
[edit] Computer Science
Computer scientists refer to arborescences as trees.
[edit] References
- Tutte, W.T. (2001), Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3.
.svg){kind=small} |
This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |
