Un Gráfico Acíclico Dirigido (DAG) es un tipo de gráfico en el que es imposible volver al mismo nodo atravesando los bordes.

En teoría de grafos, un grafo es una estructura que consiste en nodos que están conectados por aristas. Puede pensar en los nodos como puntos y los bordes como líneas dibujadas de punto a punto.

‘Dirigido’ significa que los bordes del gráfico solo se mueven en una dirección, donde los bordes futuros dependen de los anteriores. Por ejemplo, si se graficara el proceso de cocinar y comer una comida que consiste en arroz y pollo, las tareas involucradas tendrían que ordenarse topológicamente (o ordenarse topológicamente). Antes de que pueda comer la comida, debe preparar la comida, por lo que el borde necesariamente se dirigirá de la preparación hacia adelante para comer. Pero antes de que pueda preparar la comida, debe comprar los ingredientes, por lo que nuevamente el borde debe ir del evento anterior al evento posterior. Suponiendo que el arroz se comprara en un evento separado del pollo, habría dos bordes separados para los eventos de compras de comestibles que no están conectados entre sí, pero que convergen en el evento de preparación de la comida.

‘Acíclico’ significa que es imposible comenzar en un punto del gráfico y volver a él siguiendo los bordes. Mientras que un ciclo regresa a su punto de partida original como un círculo, un gráfico acíclico continúa moviéndose en una dirección lineal y nunca vuelve al punto de partida. Para continuar con el ejemplo anterior de cena de pollo y arroz, no se puede pasar en el gráfico de comprar el arroz a preparar la comida y comprar el pollo, ya que eso requeriría moverse hacia atrás a través del gráfico. Es imposible preparar el pollo si aún no lo has comprado.

Los DAG son representaciones gráficas probabilísticas de redes bayesianas que tienen como objetivo modelar la dependencia condicional (por ejemplo, comer la comida depende de prepararla primero).

Varias criptomonedas utilizan DAG en lugar de estructuras de datos de blockchain para procesar y validar transacciones. Con blockchains, todos los nodos de una red se construyen en la misma cadena de bloques única con cada bloque haciendo referencia al anterior. Una posible desventaja de esta estructura es que pone un límite al rendimiento de transacciones de la red, ya que solo hay un número limitado de transacciones que pueden caber en un solo bloque y solo un número limitado de bloques que pueden validarse en un tiempo determinado. En una red DAG, las transacciones están directamente vinculadas entre sí en lugar de agruparse en bloques, y las transacciones se pueden procesar simultáneamente con otras. El resultado es un cuello de botella reducido en el rendimiento de las transacciones.