Grafo acíclico dirigido

En ciencias de la computación y matemáticas un grafo acíclico dirigido o DAG (del inglés Directed Acyclic Graph), es un grafo dirigido que no tiene ciclos; esto significa que para cada vértice v, no hay un camino directo que empiece y termine en v.

Los DAG aparecen en modelos donde no tiene sentido que un vértice tenga un camino directo a él mismo; por ejemplo, si un arco u→v indica que v es parte de u, crear un ciclo v→u indicaría que u es subconjunto de sí mismo y de v, lo cual es imposible.

Cada DAG da lugar a un ordenamiento parcial ≤ sobre sus vértices, donde u ≤ v exactamente cuando existe un camino directo desde u a v.

En particular, la clausura transitiva es el orden de accesibilidad ≤.

Dicha longitud es igual a la máxima altura de todas las fuentes e igual a la máxima profundidad de todos los sifones.