Rooted graph

From Infogalactic: the planetary knowledge core
(Redirected from Flow graph)
Jump to: navigation, search

<templatestyles src="Module:Hatnote/styles.css"></templatestyles>

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]:454 Both directed and undirected versions of rooted graphs have been studied, and there are also variant definitions that allow multiple roots.

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.[2]:455

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.[5]:307[6] 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.[7]:122[8]:524[9][10]:308 Authors which give the more general definition, may refer to these as connected (or 1-connected) rooted digraphs.[5]:307

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

Applications

Flow graphs

In computer science, rooted graphs in which the root vertex can reach all other vertices are called flow graphs or flowgraphs.[3] Sometimes an additional restriction is added specifying that a flow graph must have a single exit (sink) vertex as well.[12]:319

Flow graphs may be viewed as abstractions of flow charts, with the non-structural elements (node contents and types) removed.[13][14] Perhaps the best known sub-class of flow graphs are control flow graphs, used in compilers and program analysis. An arbitrary flow graph may 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.[15] Another type of flow graph commonly used is the call graph, in which nodes correspond to entire subroutines.[16]

The general notion of flow graph has been called program graph,[17] but the same term has also been used to denote only control flow graphs.[18] Flow graphs have also been called unlabeled flowgraphs,[19] and proper flowgraphs.[13] These graphs are sometimes used in software testing.[13][16]

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.[12]: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.[12]:339 Theoretical research has been done on determining, for example, the proportion of prime flow graphs given a chosen set of graphs.[20]

Set theory

Peter Aczel has used rooted directed graphs in which the whole graph 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, the vertices of a graph model sets within the set theory, and their adjacency relation models the relation of one set belonging to another. The anti-foundation axiom states that every accessible pointed graph models a family of sets in this way.[21]

Combinatorial enumeration

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

Related concepts

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.[6] 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.[22]

Rooted graphs may be combined using the rooted product of graphs.[23]

See also

References

  1. Lua error in package.lua at line 80: module 'strict' not found.
  2. 2.0 2.1 Lua error in package.lua at line 80: module 'strict' not found.
  3. 3.0 3.1 Lua error in package.lua at line 80: module 'strict' not found. Cite error: Invalid <ref> tag; name "GrossYellen2013" defined multiple times with different content
  4. Lua error in package.lua at line 80: module 'strict' not found.
  5. 5.0 5.1 Lua error in package.lua at line 80: module 'strict' not found.
  6. 6.0 6.1 doi:10.1090/S0002-9939-1989-0967486-0
  7. Lua error in package.lua at line 80: module 'strict' not found.
  8. Lua error in package.lua at line 80: module 'strict' not found.
  9. Lua error in package.lua at line 80: module 'strict' not found.
  10. Lua error in package.lua at line 80: module 'strict' not found.
  11. Lua error in package.lua at line 80: module 'strict' not found.
  12. 12.0 12.1 12.2 Lua error in package.lua at line 80: module 'strict' not found.
  13. 13.0 13.1 13.2 Lua error in package.lua at line 80: module 'strict' not found.
  14. Lua error in package.lua at line 80: module 'strict' not found.
  15. Lua error in package.lua at line 80: module 'strict' not found.
  16. 16.0 16.1 Lua error in package.lua at line 80: module 'strict' not found.
  17. Lua error in package.lua at line 80: module 'strict' not found.
  18. Lua error in package.lua at line 80: module 'strict' not found.
  19. Lua error in package.lua at line 80: module 'strict' not found.
  20. Lua error in package.lua at line 80: module 'strict' not found.
  21. Lua error in package.lua at line 80: module 'strict' not found.
  22. Lua error in package.lua at line 80: module 'strict' not found..
  23. Lua error in package.lua at line 80: module 'strict' not found.

Further reading

  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.

External links