Gráfico acíclico y gráfico acíclico dirigido: definición, ejemplos

Actualizado por ultima vez el 22 de septiembre de 2021, por Luis Benites.

Un árbol con nodos ABCDEF y G.

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.

árbol de expansión mínimo

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.

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:
Gráfico Acíclico Dirigido

  • 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.

Tengo una Maestría en Ciencias en Estadística Aplicada y he trabajado en algoritmos de aprendizaje automático para empresas profesionales tanto en el sector de la salud como en el comercio minorista.

Deja un comentario

¿Qué es un coeficiente beta estandarizado? Un coeficiente beta estandarizado compara la fuerza del efecto de cada variable independiente individual…
statologos comunidad-2

Compartimos información EXCLUSIVA y GRATUITA solo para suscriptores (cursos privados, programas, consejos y mucho más)

You have Successfully Subscribed!