directed acyclic graph

English

Noun

directed acyclic graph (plural directed acyclic graphs)

1. (graph theory, computer science) A finite directed graph that contains no directed cycles.

   Synonyms: acyclic digraph, acyclic directed graph, (acronym) DAG

   Hyponyms: Bayesian network, tree

   • 1995, Volker Turan, Weimin Chen, GLB-closures in Directed Acyclic Graphs and Their Applications, Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer (editors), Graph-Theoretic Concepts in Computer Science: 20th International Workshop, Proceedings, Springer, LNCS 903, page 121,

     A subset S of the vertices of a directed acyclic graph is called glb-closed, if it contains the greatest lower bounds of all pairs of vertices of S. […] Directed acyclic graphs are widely used in different areas of computer science.

   • 2001, Peter J. Pahl, Rudolf Damrath, Mathematical Foundations of Computational Engineering: A Handbook, Springer, page 574:

     In studying these properties, a distinction is made between directed acyclic graphs with directed edges and simple acyclic graphs with undirected edges. […] A directed acyclic graph $G=(V;R)$ is asymmetric and does not contain cycles.

   • 2011, Michael Donders, Sara Miner More, Pavel Naumov, Information Flow on Directed Acyclic Graphs, Lev D. Beklemishev, Ruy de Queiroz (editors), Logic, Language, Information, and Computation: 18th International Workshop, Proceedings, Springer, LNAI 6642, page 95,

     A logical system that describes the properties of this relation for an arbitrary fixed directed acyclic graph is introduced and proven to be complete and decidable.

Translations

directed graph without cycles

• Czech: orientovaný acyklický graf m
• German: gerichteter azyklischer Graph m
• Italian: grafo aciclico diretto m, grafo aciclico orientato m, digrafo aciclico m

Further reading

• directed acyclic graph on Wikipedia.Wikipedia
• Bayesian network on Wikipedia.Wikipedia
• Acyclic Digraph on Wolfram MathWorld