Contenido de este artículo
- 0
- 0
- 0
- 0
Actualizado el 22 de septiembre de 2021, por Luis Benites.
Un árbol con nodos ABCDEF y G.
Los gráficos acíclicos dirigidos (DAG) se utilizan para modelar probabilidades, conectividad y causalidad. Un “grafo” en este sentido significa una estructura hecha de nodos y aristas.
- Los nodos generalmente se indican mediante círculos u óvalos (aunque técnicamente pueden tener cualquier forma que elija).
- Los bordes son las conexiones entre los nodos. Un borde conecta dos nodos. Suelen estar representados por líneas, o líneas con flechas.
Los DAG se basan en gráficos acíclicos básicos.
¿Qué es un gráfico acíclico?
Un gráfico acíclico es un gráfico sin ciclos (un ciclo es un circuito completo). Al seguir el gráfico de nodo a nodo, nunca visitará el mismo nodo dos veces.
Este gráfico (la línea negra gruesa) es acíclico, ya que no tiene ciclos (circuitos completos).
Un gráfico acíclico conexo, como el de arriba, se llama árbol . Si una o más de las «ramas» del árbol están desconectadas, el gráfico acíclico se llama bosque .
Este gráfico tiene un circuito completo, por lo que no es acíclico.
¿Qué es un gráfico acíclico dirigido?
Un gráfico acíclico dirigido es un gráfico acíclico que tiene una dirección así como una falta de ciclos. Las partes del gráfico anterior son:
- Entero = el conjunto de los vértices.
- Conjunto de vértices = {1,2,3,4,5,6,7}.
- Juego de aristas = {(1,2), (1,3), (2,4), (2,5), (3,6), (4,7), (5,7), (6,7 )}.
Un gráfico acíclico dirigido tiene un ordenamiento topológico . Esto significa que los nodos están ordenados de modo que el nodo inicial tenga un valor más bajo que el nodo final. Un DAG tiene un ordenamiento topológico único si tiene una ruta dirigida que contiene todos los nodos; en este caso, el orden es el mismo que el orden en que aparecen los nodos en la ruta.
En informática , los DAG también se denominan gráficos de espera . Cuando se usa un DAG para detectar un interbloqueo, ilustra que un recurso tiene que esperar a que continúe otro proceso.
Redactor del artículo
¿Te hemos ayudado?
Ayudanos ahora tú, dejanos un comentario de agradecimiento, nos ayuda a motivarnos y si te es viable puedes hacer una donación:La ayuda no cuesta nada
Por otro lado te rogamos que compartas nuestro sitio con tus amigos, compañeros de clase y colegas, la educación de calidad y gratuita debe ser difundida, recuerdalo:
