Wikipedia

User:JMP EAX/draft merge

< User:JMP EAX

In mathematics, and, in particular, in graph theory, a rooted graph is typically defined as a (undirected) graph in which one node is labelled in a special way to distinguish it from the graph's other nodes.[1][2] This special node is called the root of the graph. A special case of interest are rooted trees.

As commonly defined, particularly in computer science, rooted directed graph or rooted digraph is a more specialized notion than simply identifying a root r—there must also be a directed path from r to any node other than r.[3]: 122 [4]: 524 [5][6]: 308  Flow graph (also spelled flowgraph) is another synonym used in computer science for this notion,[3]: 122 [6]: 308  and is the common one in programming language theory.[7]

In his seminal work on non-well-founded sets, Peter Aczel uses pointed graph to refer to a digraph that has a single distinguished node, and accessible pointed graph in the case where all other nodes in the digraph can be reached from the distinguished one.[8]: 4  This latter terminology has been adopted by other authors in mathematical logic and logic in computer science.

Rooted (undirected) graphs

edit

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

Rooted graphs may be combined using the rooted product of graphs.

In topological graph theory, the notion is extended to consider multiple nodes (vertexes) 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.[9] Graphs with multiple nodes designated as roots are also of some interest in combinatorics, in the area of random graphs.[10]

Rooted directed graphs

edit

As flow graphs

edit

A flow graph is essentially an abstraction obtained from the notion of flow chart, with the non-structural elements (like node contents and types) removed.[11][12]

Perhaps the best know sub-class of flow graphs are control flow graphs (CFG), used in compilers and program analysis. An arbitrary flow graph may converted to a CFG by performing an edge contraction on every edge whose source node has outdegree 1 and whose target node has indegree 1.[13] Another type of flow graph commonly used is the call graph, in which nodes correspond to entire subroutines.[14]

The general notion of flow graph has been called program graph,[15] but the same term has also been used to denote just CFGs.[16] Flow graphs have also received a number of qualified synonyms (perhaps indented to disambiguate them from CFGs), including unlabeled flowgraphs,[17] and proper flowgraphs.[11] Flow graphs (rather than CFGs) are sometimes used in software testing.[11][14]

TODO: Introduce reducible flow graphs about here.

In the theory of structured programming, an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex as well.[18]: 319  When enriched with the single-exit property, 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.[18]: 323  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.[18]: 339  Theoretical research has been done on determining, for example, the proportion of prime flow graphs given a chosen set of graphs.[19]

More than one root

edit

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.[20] In a finite graph, the existence of such a vertex can be tested in linear time: it exists if and only if the condensation of the graph has exactly one vertex with no incoming edges. If so, the root can be chosen as any vertex in the strongly connected component corresponding to this vertex.[21]

Other applications

edit

Accessible pointed graphs are used in Aczel's anti-foundation axiom, where they model the membership structure of sets in a non-well-founded set theory.[22]

They also form the inputs for computational problems of finding an optimal spanning arborescence, that is, a rooted tree containing all vertices of a given directed graph, with all edges directed from the root towards the leaves. Such a tree exists exactly when the input is accessible and pointed.[23]

See also

edit

References

edit
  1. ^ Daniel Zwillinger (2011). CRC Standard Mathematical Tables and Formulae, 32nd Edition. CRC Press. p. 150. ISBN 978-1-4398-3550-0.
  2. ^ Edward A. Bender; S. Gill Williamson (2006). Foundations of Combinatorics with Applications (PDF). Courier Dover Publications. definition 5.10 (p. 138 in the web version). ISBN 978-0-486-15150-2.
  3. ^ a b Ramachandran, Vijaya (1988). "Fast Parallel Algorithms for Reducible Flow Graphs". Concurrent Computations: 117–138. doi:10.1007/978-1-4684-5511-3_8.
  4. ^ Okamoto, Yoshio (2003). "The forbidden minor characterization of line-search antimatroids of rooted digraphs". Discrete Applied Mathematics. 131 (2): 523–533. doi:10.1016/S0166-218X(02)00471-7.
  5. ^ Abhinandan Jain (2010). Robot and Multibody Dynamics: Analysis and Algorithms. Springer Science & Business Media. p. 136. ISBN 978-1-4419-7267-5.
  6. ^ a b Chen, Xujin (2004). "An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs". Lecture Notes in Computer Science: 306–317. doi:10.1007/978-3-540-30551-4_28.
  7. ^ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 1372. ISBN 978-1-4398-8018-0.
  8. ^ 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, MR 0940014
  9. ^ Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. pp. 764–765. ISBN 978-1-4398-8018-0.
  10. ^ Joel Spencer (2001). The Strange Logic of Random Graphs. Springer Science & Business Media. chapter 4. ISBN 978-3-540-41654-8.
  11. ^ a b c Horst Zuse (1998). A Framework of Software Measurement. Walter de Gruyter. pp. 32–33. ISBN 978-3-11-080730-1.
  12. ^ Angelina Samaroo; Geoff Thompson; Peter Williams (2010). Software Testing: An ISTQB-ISEB Foundation Guide. BCS, The Chartered Institute. p. 108. ISBN 978-1-906124-76-2.
  13. ^ Peri L. Tarr; Alexander L. Wolf (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. p. 58. ISBN 978-3-642-19823-6.
  14. ^ a b Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.
  15. ^ K. Thulasiraman; M. N. S. Swamy (1992). Graphs: Theory and Algorithms. John Wiley & Sons. p. 361. ISBN 978-0-471-51356-8.
  16. ^ Alejandra Cechich; Mario Piattini; Antonio Vallecillo (2003). Component-Based Software Quality: Methods and Techniques. Springer Science & Business Media. p. 105. ISBN 978-3-540-40503-0.
  17. ^ Lowell W. Beineke; Robin J. Wilson (1997). Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics. Clarendon Press. p. 237. ISBN 978-0-19-851497-8.
  18. ^ a b c Norman Elliott Fenton; Gillian A. Hill (1993). Systems Construction and Analysis: A Mathematical and Logical Framework. McGraw-Hill. ISBN 978-0-07-707431-9.
  19. ^ Cooper, C. (2008). "Asymptotic Enumeration of Predicate-Junction Flowgraphs". Combinatorics, Probability and Computing. 5 (3): 215. doi:10.1017/S0963548300001991.
  20. ^ Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 372. ISBN 0-201-89683-4.
  21. ^ Gabow, Harold N.; Myers, Eugene W. (1978), "Finding all spanning trees of directed and undirected graphs", SIAM Journal on Computing, 7 (3): 280–287, doi:10.1137/0207024, MR 0495152.
  22. ^ 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, MR 0940014
  23. ^ 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.
edit
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:JMP_EAX/draft_merge&oldid=695237687"