b'\n_START_ARTICLE_\nGrafo ac\xc3\xadclico dirigido\n_START_PARAGRAPH_\nEn ciencias de la computaci\xc3\xb3n y matem\xc3\xa1ticas un grafo ac\xc3\xadclico dirigido o DAG (del  ingl\xc3\xa9s Directed Acyclic Graph), es un grafo dirigido que no tiene ciclos; esto significa que para cada v\xc3\xa9rtice v, no hay un camino directo que empiece y termine en v. Los DAG aparecen en modelos donde no tiene sentido que un v\xc3\xa9rtice tenga un camino directo a \xc3\xa9l mismo; por ejemplo, si un arco u\xe2\x86\x92v indica que v es parte de u, crear un ciclo v\xe2\x86\x92u indicar\xc3\xada que u es subconjunto de s\xc3\xad mismo y de v, lo cual es imposible. Informalmente un DAG "fluye" en solo una direcci\xc3\xb3n._NEWLINE_Cada DAG da lugar a un ordenamiento parcial \xe2\x89\xa4 sobre sus v\xc3\xa9rtices, donde u \xe2\x89\xa4 v exactamente cuando existe un camino directo desde u a v. Muchos DAG pueden generar el mismo ordenamiento parcial de los v\xc3\xa9rtices siendo el de menor n\xc3\xbamero de arcos denominado la reducci\xc3\xb3n transitiva y el que mayor n\xc3\xbamero de arcos la Clausura transitiva. En particular, la clausura transitiva es el orden de accesibilidad \xe2\x89\xa4.\n_START_SECTION_\nTerminolog\xc3\xada\n_START_PARAGRAPH_\nUna fuente es un v\xc3\xa9rtice sin flujos (relaciones) de entrada, mientras que un sif\xc3\xb3n o sumidero es un v\xc3\xa9rtice sin flujos (relaciones) de salida._NEWLINE_Un DAG finito tiene por lo menos una fuente y un sif\xc3\xb3n._NEWLINE_La profundidad de un v\xc3\xa9rtice, en un DAG finito, es la longitud del camino m\xc3\xa1s largo que existe desde una fuente a dicho v\xc3\xa9rtice, la altura de un v\xc3\xa9rtice es la longitud m\xc3\xa1s larga del camino que exista desde el v\xc3\xa9rtice a un sif\xc3\xb3n._NEWLINE_La longitud de un DAG finito es la longitud (n\xc3\xbamero de arcos) del camino directo m\xc3\xa1s largo. Dicha longitud es igual a la m\xc3\xa1xima altura de todas las fuentes e igual a la m\xc3\xa1xima profundidad de todos los sifones.'