Directed acyclic graph (DAG)

A directed acyclic graph (DAG) is a directed graph in which there are no directed cycles, i.e., it is not possible to arrive at the same node where one started by following only edges in the direction into which they are pointing.

For instance, the directed graph below is a DAG even though there is an (undirected) cycle B-D-E-C-B because any traversal of the cycle requires that one travels against the direction of at least one edge.

Stemmata (as long as they are oriented) can be represented as DAGs, and each case of contamination will result in a cycle in the graph.

Illustration

In other languages

DE: gerichteter azyklischer Graph
 FR: graphe orienté acyclique
 IT: grafo aciclico orientato

TR