En ciencias de la computación y matemáticas un grafo acíclico dirigido o DAG (del inglésDirected Acyclic Graph), es un grafo dirigido que no tiene ciclos; esto significa que para cada vérticev, 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 DAGfinito 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.
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.
Datos:Q1195339
Multimedia:Directed acyclic graphs
Septiembre 25, 2021
grafo, acíclico, dirigido, ciencias, computación, matemáticas, grafo, acíclico, dirigido, inglés, directed, acyclic, graph, grafo, dirigido, tiene, ciclos, esto, significa, para, cada, vértice, camino, directo, empiece, termine, aparecen, modelos, donde, tiene. En ciencias de la computacion y matematicas un grafo aciclico dirigido o DAG del ingles Directed Acyclic Graph es un grafo dirigido que no tiene ciclos esto significa que para cada vertice v no hay un camino directo que empiece y termine en v Los DAG aparecen en modelos donde no tiene sentido que un vertice tenga un camino directo a el mismo por ejemplo si un arco u v indica que v es parte de u crear un ciclo v u indicaria que u es subconjunto de si mismo y de v lo cual es imposible Informalmente un DAG fluye en solo una direccion Cada DAG da lugar a un ordenamiento parcial sobre sus vertices donde u v exactamente cuando existe un camino directo desde u a v Muchos DAG pueden generar el mismo ordenamiento parcial de los vertices siendo el de menor numero de arcos denominado la reduccion transitiva y el que mayor numero de arcos la Clausura transitiva En particular la clausura transitiva es el orden de accesibilidad Terminologia EditarUna fuente es un vertice sin flujos relaciones de entrada mientras que un sifon o sumidero es un vertice sin flujos relaciones de salida Un DAG finito tiene por lo menos una fuente y un sifon La profundidad de un vertice en un DAG finito es la longitud del camino mas largo que existe desde una fuente a dicho vertice la altura de un vertice es la longitud mas larga del camino que exista desde el vertice a un sifon La longitud de un DAG finito es la longitud numero de arcos del camino directo mas largo Dicha longitud es igual a la maxima altura de todas las fuentes e igual a la maxima profundidad de todos los sifones Vease tambien EditarArbol teoria de grafos Enlaces externos EditarWeisstein Eric W Acyclic Digraph En Weisstein Eric W ed MathWorld en ingles Wolfram Research Consultado el 27 de mayo de 2010 Instituto Estadounidense de Estandares y Tecnologia http www wutka com dawg html Enumerating the Directed Graphs por Seth J Chandler con Matthew Szudzik y Jesse Nochella Datos Q1195339 Multimedia Directed acyclic graphsObtenido de https es wikipedia org w index php title Grafo aciclico dirigido amp oldid 120193959, wikipedia, wiki, leyendo, leer, libro, biblioteca,
