Rooted graph
In
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
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).
Applications
Flow graphs
In
Flow graphs may be viewed as
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[
Combinatorial enumeration
The number of rooted undirected graphs for 1, 2, ... nodes is 1, 2, 6, 20, 90, 544, ... (sequence A000666 in the OEIS).
Related concepts
A special case of interest are
Rooted graphs may be combined using the rooted product of graphs.[27]
See also
References
- ISBN 978-1-4398-3550-0
- MR 0068198. See p. 454.
- ISBN 978-1-4398-8018-0
- ISBN 978-3-540-41654-8
- ^ Harary (1955, p. 455).
- ^ 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. - ^ ,
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.
- ISBN 978-1-4684-5513-7,
A rooted directed graph or a flow graph G = (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. - ,
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. - 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.
- S2CID 5235131
- 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.
- ^ Gross, Yellen & Zhang (2013, p. 1372).
- ISBN 978-0-07-707431-9.
- ^ ISBN 978-3-11-080730-1
- ISBN 978-1-906124-76-2
- ISBN 978-3-642-19823-6
- ^ ISBN 978-0-387-94899-7
- ISBN 978-0-471-51356-8
- ISBN 978-3-540-40503-0
- ISBN 978-0-19-851497-8
- ^ Fenton & Hill (1993, p. 323).
- ^ Fenton & Hill (1993, p. 339).
- S2CID 10313545
- MR 0940014, archived from the original(PDF) on 2015-03-26
- S2CID 13987985.
- MR 0494910
Further reading
- McMahon, Elizabeth W. (1993), "On the greedoid polynomial for rooted graphs and rooted digraphs", Journal of Graph Theory, 17 (3): 433–442,
- Gordon, Gary (2001), "A characteristic polynomial for rooted graphs and rooted digraphs", Discrete Mathematics, 232 (1–3): 19–33,