Rooted graph

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

[13] Sometimes an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex.

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

[24] 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.

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

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 .