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. Informalmente un DAG "fluye" en solo una dirección.

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. Muchos DAG pueden generar el mismo ordenamiento parcial de los vértices siendo el de menor número de arcos denominado la reducción transitiva y el que mayor número de arcos la Clausura transitiva. En particular, la clausura transitiva es el orden de accesibilidad ≤.

Terminología

Una fuente es un vértice sin flujos (relaciones) de entrada, mientras que un sifón o sumidero es un vértice sin flujos (relaciones) de salida.

Un DAG finito tiene por lo menos una fuente y un sifón.

La profundidad de un vértice, en un DAG finito, es la longitud del camino más largo que existe desde una fuente a dicho vértice, la altura de un vértice es la longitud más larga del camino que exista desde el vértice a un sifón.

La longitud de un DAG finito es la longitud (número de arcos) del camino directo más largo. Dicha longitud es igual a la máxima altura de todas las fuentes e igual a la máxima profundidad de todos los sifones.

Véase también

• Árbol (teoría de grafos)

Enlaces externos

• Weisstein, Eric W. «Acyclic Digraph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. Consultado el 27 de mayo de 2010. 
• Instituto Estadounidense de Estándares y Tecnología
• http://www.wutka.com/dawg.html
• Enumerating the Directed Graphs por Seth J. Chandler con Matthew Szudzik y Jesse Nochella.