Arborescence (graph theory)

Last updated

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

Contents

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

Related Research Articles

<span class="mw-page-title-main">Binary tree</span> Limited form of tree data structure

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree with k = 2. A recursive definition using set theory is that a binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

<span class="mw-page-title-main">Tree (data structure)</span> Abstract data type simulating a hierarchical tree structure and represented as a set of linked nodes

In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent. These constraints mean there are no cycles or "loops", and also that each child can be treated like the root node of its own subtree, making recursion a useful technique for tree traversal. In contrast to linear data structures, many trees cannot be represented by relationships between neighboring nodes in a single straight line.

<span class="mw-page-title-main">Tree (graph theory)</span> Undirected, connected and acyclic graph

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Spanning tree</span> Tree which includes all vertices of a graph

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Path (graph theory)</span> Sequence of edges which join a sequence of nodes on a given graph

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

In mathematics, and, in particular, in graph theory, a rooted graph is a graph in which one vertex has been distinguished as the root. Both directed and undirected versions of rooted graphs have been studied, and there are also variant definitions that allow multiple roots.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Jack Edmonds</span> American/Canadian mathematician and computer scientist

Jack R. Edmonds is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, polyhedral combinatorics, discrete mathematics and the theory of computing. He was the recipient of the 1985 John von Neumann Theory Prize.

<span class="mw-page-title-main">Series–parallel graph</span> Recursively-formed graph with two terminal vertices

In graph theory, series–parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.

In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight . It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).

<span class="mw-page-title-main">Directed graph</span> Graph with oriented edges

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

Bernhard H. Korte is a German mathematician and computer scientist, a professor at the University of Bonn, and an expert in combinatorial optimization.

In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.

Algorithms and Combinatorics is a book series in mathematics, and particularly in combinatorics and the design and analysis of algorithms. It is published by Springer Science+Business Media, and was founded in 1987.

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. 1 2 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. 1 2 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. 1 2 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. 1 2 3 Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN   3-540-44389-4.
  13. 1 2 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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.