Editing Rooted graph (section)

==Applications==
===Flow graphs===
In [[computer science]], rooted graphs in which the root vertex can reach all other vertices are called '''flow graphs''' or '''flowgraphs'''.<ref>{{harvtxt|Gross|Yellen|Zhang|2013|page=1372}}.</ref> Sometimes an additional restriction is added specifying that a flow graph must have a single exit ([[sink (graph theory)|sink]]) vertex.<ref>{{citation|first1=Norman Elliott|last1=Fenton|first2=Gillian A.|last2=Hill|title=Systems Construction and Analysis: A Mathematical and Logical Framework|year=1993|publisher=McGraw-Hill|isbn=978-0-07-707431-9|page=319}}.</ref>

Flow graphs may be viewed as [[abstraction]]s of [[flow chart]]s, with the non-structural elements (node contents and types) removed.<ref name="Zuse1998"/><ref>{{citation|first1=Angelina|last1=Samaroo|first2=Geoff|last2=Thompson|first3=Peter|last3=Williams|title=Software Testing: An ISTQB-ISEB Foundation Guide|year=2010|publisher=BCS, The Chartered Institute|isbn=978-1-906124-76-2|page=108}}</ref> Perhaps the best known sub-class of flow graphs are [[control-flow graph]]s, used in [[compiler]]s 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.<ref>{{citation|first1=Peri L.|last1=Tarr|first2=Alexander L.|last2=Wolf|title=Engineering of Software: The Continuing Contributions of Leon J. Osterweil|year=2011|publisher=Springer Science & Business Media|isbn=978-3-642-19823-6|page=58}}</ref> Another type of flow graph commonly used is the [[call graph]], in which nodes correspond to entire [[subroutine]]s.<ref name="Jalote1997"/>

The general notion of flow graph has been called '''program graph''',<ref>{{citation|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|title=Graphs: Theory and Algorithms|year=1992|publisher=John Wiley & Sons|isbn=978-0-471-51356-8|page=361}}</ref> but the same term has also been used to denote only control-flow graphs.<ref>{{citation|first1=Alejandra|last1=Cechich|first2=Mario|last2=Piattini|first3=Antonio|last3=Vallecillo|title=Component-Based Software Quality: Methods and Techniques|year=2003|publisher=Springer Science & Business Media|isbn=978-3-540-40503-0|page=105}}</ref> Flow graphs have also been called '''unlabeled flowgraphs'''<ref>{{citation|first1=Lowell W.|last1=Beineke|first2=Robin J.|last2=Wilson|title=Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics|year=1997|publisher=Clarendon Press|isbn=978-0-19-851497-8|page=[https://archive.org/details/graphconnections0000unse/page/237 237]|url=https://archive.org/details/graphconnections0000unse/page/237}}</ref> and '''proper flowgraphs'''.<ref name="Zuse1998"/> These graphs are sometimes used in [[software testing]].<ref name="Zuse1998">{{citation|first=Horst|last=Zuse|title=A Framework of Software Measurement|year=1998|publisher=Walter de Gruyter|isbn=978-3-11-080730-1|pages=32–33}}</ref><ref name="Jalote1997">{{citation|first=Pankaj|last=Jalote|title=An Integrated Approach to Software Engineering|year=1997|publisher=Springer Science & Business Media|isbn=978-0-387-94899-7|page=[https://archive.org/details/integratedapproa0000jalo/page/372 372]|url-access=registration|url=https://archive.org/details/integratedapproa0000jalo/page/372}}</ref>

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.<ref>{{harvtxt|Fenton|Hill|1993|page=323}}.</ref> ''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]].<ref>{{harvtxt|Fenton|Hill|1993|page=339}}.</ref> Theoretical research has been done on determining, for example, the proportion of prime flow graphs given a chosen set of graphs.<ref>{{citation | doi = 10.1017/S0963548300001991| title = Asymptotic Enumeration of Predicate-Junction Flowgraphs| journal = [[Combinatorics, Probability and Computing]]| volume = 5| issue = 3| pages = 215–226| year = 2008| last1 = Cooper | first1 = C.| s2cid = 10313545}}</ref>

===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.<ref>{{Citation |mr=0940014 |authorlink=Peter Aczel |last=Aczel |first=Peter |title=Non-well-founded sets |series=CSLI Lecture Notes |volume=14 |publisher=Stanford University, Center for the Study of Language and Information |place=Stanford, CA |year=1988 |isbn=0-937073-22-9 <!--Pbk; hardcover is -21-0 --> |lccn=87-17857 |url=http://standish.stanford.edu/pdf/00000056.pdf |url-status=dead |archive-url=https://web.archive.org/web/20150326130152if_/http://standish.stanford.edu/pdf/00000056.pdf |archive-date=2015-03-26}}</ref>

===Combinatorial game theory===
Any [[Combinatorial game theory|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 [[Game complexity#State-space complexity|state-space complexity]] is the number of vertices in the graph.