frame|Un DAG simple. En ciències de la computació i matemàtiques, un graf acíclic dirigit, conegut com a DAG (directed acyclic graph) per les sigles en anglès, és un graf dirigit que no té cicles. Això significa que per a cada vèrtex v, no hi ha un camí directe que comenci i acabi en v. Els DAG apareixen en models en què no té sentit que un vèrtex tingui un camí directe a si mateix, per exemple, si un arc o → v indica que v és part de o, crear un cicle v→o indicaria que o és subconjunt de si mateix i de v, la qual cosa és impossible. Informalment, un DAG "flueix" en només una direcció.
Cada DAG dona lloc a un ordenament parcial ≤ sobre els seus vèrtexs, on o ≤ v exactament quan hi ha un camí directe des de o a v. Molts DAG poden generar el mateix ordenament parcial dels vèrtexs; el de nombre més baix d'arcs és anomenat la reducció transitiva, i el de nombre més alt d'arcs, la clausura transitiva. En particular, la clausura transitiva és l'ordre d'accessibilitat ≤.
Terminologia Una font (souce) és un vèrtex sense fluxos (relacions) d'entrada, mentre que un pou (sink) és un vèrtex sense fluxos (relacions) de sortida.
Un DAG finit té com a mínim una font i un pou.
La profunditat d'un vèrtex, en un DAG finit, és la longitud del camí més llarg que hi ha des d'una font a aquest vèrtex, l'altura d'un vèrtex és la longitud més llarga del camí que hi hagi des del vèrtex a un pou.
La longitud d'un DAG finit és la longitud (nombre d'arcs) del camí directe més llarg. Aquesta longitud és igual a la màxima altura de totes les fonts i igual a la màxima profunditat de tots els sifons.
Vegeu també Arbre (teoria de grafs)
Enllaços externs Gràfics acíclics a MathWorld Institut Americà d'Estàndards i Tecnologia http://www.wutka.com/dawg.html
Categoria:Famílies de grafs