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

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 these[ clarification needed (these ___?)] 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

Given a purely[ clarification needed ; is there a definition somewhere?] combinatorial game, there is an associated rooted directed graph whose vertices are game positions and whose edges are moves, and graph traversal starting from the root is used to create a game tree. If the graph contains directed cycles, then a position in the game could repeat infinitely many times, and rules are usually needed to prevent the game from continuing indefinitely. Otherwise, the graph is a directed acyclic graph, and if it isn't a rooted tree, then the game has transpositions. This graph and its topology are important in the study of game complexity, where the state-space complexity is the number of vertices in the graph, the average game length is the average number of vertices traversed from the root to a vertex with no direct successors, and the average branching factor of a game tree is the average outdegree of 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 (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, 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).

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, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical 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. Graphs are one of the objects of study in discrete mathematics.

<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">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 an arbitrary 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)).

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance or shortest-path distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

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

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

<span class="mw-page-title-main">Shortest-path tree</span>

In mathematics and computer science, a shortest-path tree rooted at a vertex v of a connected, undirected graph G is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G.

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

In graph theory, an arborescence is a directed graph in which, for a vertex u and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph.

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

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.