Rooted graph

Last updated

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

Contents

Examples of rooted graphs with some variants. A digraph with the root placed such that each vertex has exactly one path directed to it from the root is an arborescence. Rooted graphs.png
Examples of rooted graphs with some variants. A digraph with the root placed such that each vertex has exactly one path directed to it from the root is an arborescence.

Rooted graphs may also be known (depending on their application) as pointed graphs or flow graphs. In some of the applications of these graphs, there is an additional requirement that the whole graph be reachable from the root vertex.

Variations

In topological graph theory, the notion of a rooted graph may be extended to consider multiple vertices or multiple edges as roots. The former are sometimes called vertex-rooted graphs in order to distinguish them from edge-rooted graphs in this context. [3] Graphs with multiple nodes designated as roots are also of some interest in combinatorics, in the area of random graphs. [4] These graphs are also called multiply rooted graphs. [5]

The terms rooted directed graph or rooted digraph also see variation in definitions. The obvious transplant is to consider a digraph rooted by identifying a particular node as root. [6] [7] However, in computer science, these terms commonly refer to a narrower notion; namely, a rooted directed graph is a digraph with a distinguished node r, such that there is a directed path from r to any node other than r. [8] [9] [10] [11] Authors who give the more general definition may refer to graphs meeting the narrower definition as connected rooted digraphs [6] or accessible rooted graphs (see § Set theory).

The Art of Computer Programming defines rooted digraphs slightly more broadly, namely, a directed graph is called rooted if it has at least one node that can reach all the other nodes. Knuth notes that the notion thus defined is a sort of intermediate between the notions of strongly connected and connected digraph. [12]

Applications

Flow graphs

In computer science, rooted graphs in which the root vertex can reach all other vertices are called flow graphs or flowgraphs. [13] Sometimes an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex. [14]

Flow graphs may be viewed as abstractions of flow charts, with the non-structural elements (node contents and types) removed. [15] [16] Perhaps the best known sub-class of flow graphs are control-flow graphs, used in compilers and program analysis. An arbitrary flow graph may be converted to a control-flow graph by performing an edge contraction on every edge that is the only outgoing edge from its source and the only incoming edge into its target. [17] Another type of flow graph commonly used is the call graph, in which nodes correspond to entire subroutines. [18]

The general notion of flow graph has been called program graph, [19] but the same term has also been used to denote only control-flow graphs. [20] Flow graphs have also been called unlabeled flowgraphs [21] and proper flowgraphs. [15] These graphs are sometimes used in software testing. [15] [18]

When required to have a single exit, flow graphs have two properties not shared with directed graphs in general: flow graphs can be nested, which is the equivalent of a subroutine call (although there is no notion of passing parameters), and flow graphs can also be sequenced, which is the equivalent of sequential execution of two pieces of code. [22] Prime flow graphs are defined as flow graphs that cannot be decomposed via nesting or sequencing using a chosen pattern of subgraphs, for example the primitives of structured programming. [23] Theoretical research has been done on determining, for example, the proportion of prime flow graphs given a chosen set of graphs. [24]

Set theory

Peter Aczel has used rooted directed graphs such that every node is reachable from the root (which he calls accessible pointed graphs) to formulate Aczel's anti-foundation axiom in non-well-founded set theory. In this context, each vertex of an accessible pointed graph models a (non-well-founded) set within Aczel's (non-well-founded) set theory, and an arc from a vertex v to a vertex w models that v is an element of w. Aczel's anti-foundation axiom states that every accessible pointed graph models a family of (non-well-founded) sets in this way. [25]

Combinatorial game theory

Any combinatorial game, can be associated with a rooted directed graph whose vertices are game positions, whose edges are moves, and whose root is the starting position of the game. This graph is important in the study of game complexity, where the state-space complexity is the number of vertices in the graph.

Combinatorial enumeration

The number of rooted undirected graphs for 1, 2, ... nodes is 1, 2, 6, 20, 90, 544, ... (sequence A000666 in the OEIS ).

A special case of interest are rooted trees, the trees with a distinguished root vertex. If the directed paths from the root in the rooted digraph are additionally restricted to be unique, then the notion obtained is that of (rooted) arborescence—the directed-graph equivalent of a rooted tree. [7] A rooted graph contains an arborescence with the same root if and only if the whole graph can be reached from the root, and computer scientists have studied algorithmic problems of finding optimal arborescences. [26]

Rooted graphs may be combined using the rooted product of graphs. [27]

See also

Related Research Articles

<span class="mw-page-title-main">Tree (abstract data type)</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">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">Graph isomorphism</span> Bijection between the vertex set of two graphs

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

<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">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E )).

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

<span class="mw-page-title-main">Connectivity (graph theory)</span> Basic concept of graph theory

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

<span class="mw-page-title-main">Multigraph</span> Graph with multiple edges between two vertices

In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

In computer science, graph traversal refers to the process of visiting each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.

<i>k</i>-vertex-connected graph Graph which remains connected when k or fewer nodes removed

In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

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">Arborescence (graph theory)</span> Directed graph where every node has exactly one path to it from the root

In graph theory, an arborescence is a directed graph where there exists a vertex r such that, for any other vertex v, there is exactly one directed walk from r to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. An arborescence is also a directed rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist.

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

In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight. For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA).

References

  1. ↑ Zwillinger, Daniel (2011), CRC Standard Mathematical Tables and Formulae, 32nd Edition, CRC Press, p. 150, ISBN   978-1-4398-3550-0
  2. ↑ Harary, Frank (1955), "The number of linear, directed, rooted, and connected graphs", Transactions of the American Mathematical Society , 78 (2): 445–463, doi: 10.1090/S0002-9947-1955-0068198-2 , MR   0068198 . See p. 454.
  3. ↑ Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013), Handbook of Graph Theory (2nd ed.), CRC Press, pp. 764–765, ISBN   978-1-4398-8018-0
  4. ↑ Spencer, Joel (2001), The Strange Logic of Random Graphs, Springer Science & Business Media, chapter 4, ISBN   978-3-540-41654-8
  5. ↑ Harary (1955 , p. 455).
  6. 1 2 Björner, Anders; Ziegler, Günter M. (1992), "8. Introduction to greedoids" (PDF), in White, Neil (ed.), Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge: Cambridge University Press, pp.  284–357, doi:10.1017/CBO9780511662041.009, ISBN   0-521-38165-7, MR   1165537, Zbl   0772.05026, In this context a rooted digraph Δ = (V,E,r) is called connected (or 1-connected) if there is a directed path from the root to every vertex. See in particular p. 307.
  7. 1 2 Gordon, Gary; McMahon, Elizabeth (February 1989), "A greedoid polynomial which distinguishes rooted arborescences" (PDF), Proceedings of the American Mathematical Society , 107 (2): 287, CiteSeerX   10.1.1.308.2526 , doi: 10.1090/s0002-9939-1989-0967486-0 , A rooted subdigraph F is a rooted arborescence if the root vertex ∗ is in F and, for every vertex v in F, there is a unique directed path in F from ∗ to v. Thus, rooted arborescences in digraphs correspond to rooted trees in undirected graphs.
  8. ↑ Ramachandran, Vijaya (1988), "Fast Parallel Algorithms for Reducible Flow Graphs", Concurrent Computations: 117–138, doi:10.1007/978-1-4684-5511-3_8, ISBN   978-1-4684-5513-7, A rooted directed graph or a flow graphG = (V, A, r) is a directed graph with a distinguished vertex r such that there is a directed path in G from r to every vertex v in V − r.. See in particular p. 122.
  9. ↑ Okamoto, Yoshio; Nakamura, Masataka (2003), "The forbidden minor characterization of line-search antimatroids of rooted digraphs" (PDF), Discrete Applied Mathematics, 131 (2): 523–533, doi: 10.1016/S0166-218X(02)00471-7 , A rooted digraph is a triple G=(V,E,r) where (V ∪ {r}, E) is a digraph and r is a specified vertex called the root such that there exists a path from r to every vertex of V.. See in particular p. 524.
  10. ↑ Jain, Abhinandan (2010), Robot and Multibody Dynamics: Analysis and Algorithms, Springer Science & Business Media, p. 136, ISBN   978-1-4419-7267-5, A rooted digraph is a connected digraph with a single root node that is the ancestor of every other node in the digraph.
  11. ↑ Chen, Xujin; Zang, Wenan (2006), "An efficient algorithm for finding maximum cycle packings in reducible flow graphs", Algorithmica, 44 (3): 195–211, doi:10.1007/s00453-005-1174-x, hdl: 10722/48600 , MR   2199991, S2CID   5235131
  12. ↑ Knuth, Donald (1997), "2.3.4.2. Oriented trees", The Art of Computer Programming , vol. 1 (3rd ed.), Pearson Education, p. 372, ISBN   0-201-89683-4, It is said to be rooted if there is at least one root, that is, at least one vertex R such that there is an oriented path from V to R for all V ≠ R.
  13. ↑ Gross, Yellen & Zhang (2013 , p. 1372).
  14. ↑ Fenton, Norman Elliott; Hill, Gillian A. (1993), Systems Construction and Analysis: A Mathematical and Logical Framework, McGraw-Hill, p. 319, ISBN   978-0-07-707431-9 .
  15. 1 2 3 Zuse, Horst (1998), A Framework of Software Measurement, Walter de Gruyter, pp. 32–33, ISBN   978-3-11-080730-1
  16. ↑ Samaroo, Angelina; Thompson, Geoff; Williams, Peter (2010), Software Testing: An ISTQB-ISEB Foundation Guide, BCS, The Chartered Institute, p. 108, ISBN   978-1-906124-76-2
  17. ↑ Tarr, Peri L.; Wolf, Alexander L. (2011), Engineering of Software: The Continuing Contributions of Leon J. Osterweil, Springer Science & Business Media, p. 58, ISBN   978-3-642-19823-6
  18. 1 2 Jalote, Pankaj (1997), An Integrated Approach to Software Engineering , Springer Science & Business Media, p.  372, ISBN   978-0-387-94899-7
  19. ↑ Thulasiraman, K.; Swamy, M. N. S. (1992), Graphs: Theory and Algorithms, John Wiley & Sons, p. 361, ISBN   978-0-471-51356-8
  20. ↑ Cechich, Alejandra; Piattini, Mario; Vallecillo, Antonio (2003), Component-Based Software Quality: Methods and Techniques, Springer Science & Business Media, p. 105, ISBN   978-3-540-40503-0
  21. ↑ Beineke, Lowell W.; Wilson, Robin J. (1997), Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics, Clarendon Press, p.  237, ISBN   978-0-19-851497-8
  22. ↑ Fenton & Hill (1993 , p. 323).
  23. ↑ Fenton & Hill (1993 , p. 339).
  24. ↑ Cooper, C. (2008), "Asymptotic Enumeration of Predicate-Junction Flowgraphs", Combinatorics, Probability and Computing , 5 (3): 215–226, doi:10.1017/S0963548300001991, S2CID   10313545
  25. ↑ Aczel, Peter (1988), Non-well-founded sets (PDF), CSLI Lecture Notes, vol. 14, Stanford, CA: Stanford University, Center for the Study of Language and Information, ISBN   0-937073-22-9, LCCN   87-17857, MR   0940014, archived from the original (PDF) on 2015-03-26
  26. ↑ Drescher, Matthew; Vetta, Adrian (2010), "An Approximation Algorithm for the Maximum Leaf Spanning Arborescence Problem", ACM Trans. Algorithms, 6 (3): 46:1–46:18, doi:10.1145/1798596.1798599, S2CID   13987985 .
  27. ↑ Godsil, C. D.; McKay, B. D. (1978), "A new graph product and its spectrum" (PDF), Bull. Austral. Math. Soc., 18 (1): 21–28, doi: 10.1017/S0004972700007760 , MR   0494910

Further reading

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.