Arborescence (graph theory)

Last updated

In graph theory, an arborescence is a directed graph where there exists a vertex r (called the root) such that, for any other vertex v, there is exactly one directed walk from v to r (noting that the root r is unique). [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">Tree (data structure)</span> Linked node hierarchical data structure

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">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

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

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">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">Factor-critical graph</span> Graph of n vertices with a perfect matching for every subgraph of n-1 vertices

In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every induced subgraph of n − 1 vertices has a perfect matching.

<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">Hypohamiltonian graph</span> Type of graph in graph theory

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

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

<span class="mw-page-title-main">3-dimensional matching</span>

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.

<span class="mw-page-title-main">Multitree</span> Directed acyclic graph with ≤1 directed paths between any two nodes

In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

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.

<span class="mw-page-title-main">Ear decomposition</span> Partition of graph into sequence of paths

In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.

Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.

References

  1. ↑ Darij Grinberg (2 August 2023). "An introduction to graph theory (Text for Math 530 in Spring 2022 at Drexel University)" (PDF). Darij Grinberg, Ludwig-Maximilians-Universität München. p. 187. Retrieved 2 July 2024. Theorem 5.6.5, Statement A4: For each vertex v ∈ V, the multidigraph D has a unique walk from r to v.
  2. ↑ Gordon, Gary (1989). "A greedoid polynomial which distinguishes rooted arborescences". Proceedings of the American Mathematical Society. 107 (2): 287–298. 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   978-1-4008-3535-5.
  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.