Terminología de grafos dirigidos acíclicos

Un DAG (grafo dirigido acíclico) es una red de puntos llamados nodos, conectados por flechas de un solo sentido llamadas aristas: si sigues las flechas, nunca puedes volver al punto de partida, porque no hay ciclos. Piensa en un árbol genealógico: una flecha va de un padre a su hijo, pero nadie puede ser su propio abuelo. Esta estructura hace que los DAG sean ideales para representar situaciones en las que el orden importa, como las tareas previas necesarias en un proyecto o las cadenas de causa y efecto en la ciencia. Los nodos representan elementos o sucesos, las aristas muestran relaciones o dependencias y, como no hay ciclos, siempre existe al menos una forma válida de ordenar todo de principio a fin. Prueba esto: cuando planifiques tu próximo proyecto, dibuja qué tareas dependen de otras; estarás dibujando un DAG.

La terminología de los DAG te permite hablar con precisión de estructuras en las que unos elementos apuntan a otros sin formar ciclos. Los nodos, también llamados vértices, son los componentes básicos: pueden representar tareas, variables, sucesos o cualquier entidad de interés. Las aristas, o arcos, son las conexiones dirigidas entre nodos y siempre apuntan desde un origen hacia un destino. Cuando puedes seguir aristas de un nodo a otro, has encontrado un camino: el nodo de origen es un ancestro y el de destino es un descendiente.

Esta terminología resulta útil porque permite expresar qué debe ocurrir antes y qué causa qué. En la gestión de proyectos, si una tarea A debe terminar antes de que empiece una tarea B, se representa con una arista de A a B. En la inferencia causal, una flecha de X a Y indica que X influye en Y. La regla que impide los ciclos es crucial: garantiza que siempre exista al menos un orden topológico válido, es decir, una forma de colocar todos los nodos en una fila de modo que cada arista apunte hacia delante. Por eso los sistemas de compilación, los flujos de procesamiento de datos y los planificadores usan DAG: garantizan que se puedan resolver las dependencias sin quedar atrapados en dependencias circulares.

La terminología de los DAG también incluye varios conceptos especializados. Un nodo fuente no tiene aristas entrantes, es decir, nada apunta hacia él, por lo que es un punto de partida natural. Un nodo sumidero no tiene aristas salientes, es decir, ninguna flecha sale de él, por lo que marca un punto final. La clausura transitiva de un DAG añade todas las conexiones indirectas como aristas directas: si A apunta a B y B apunta a C, la clausura añade una arista de A a C. La reducción transitiva hace lo contrario: elimina las aristas redundantes para conservar solo las relaciones esenciales. En conjunto, estos términos te dan un vocabulario completo para analizar y modificar estructuras de dependencias en informática, ingeniería de datos, razonamiento causal y otros ámbitos.

La terminología de los DAG tiene su origen en la teoría de grafos, dentro de las matemáticas discretas, y se ha formalizado en la literatura de informática. Bang-Jensen y Gutin (2008) ofrecen definiciones completas de los grafos dirigidos, distinguen entre vértices (nodos) y arcos (aristas dirigidas), y establecen las propiedades formales de la alcanzabilidad, los ancestros y los descendientes en las estructuras de los DAG [1]. Cormen et al. (2022), en su libro de referencia sobre algoritmos, definen el orden topológico como una disposición lineal de los vértices en la que cada arista dirigida apunta desde un vértice anterior hacia uno posterior, y demuestran que un grafo es acíclico si y solo si existe un orden topológico [2].

Aportaciones clave sobre la terminología:

• Pearl (2009): formaliza los DAG causales, en los que los nodos representan variables aleatorias y las aristas representan influencias causales directas, y establece las relaciones entre ancestros y descendientes como base de los algoritmos de inferencia causal [3].
• Bang-Jensen y Gutin (2008): definen la clausura transitiva de un DAG como el grafo que contiene una arista de u a v siempre que se pueda llegar a v desde u, y la reducción transitiva como el subgrafo mínimo que conserva todas las relaciones de alcanzabilidad [1].
• Cormen et al. (2022): muestran que el ordenamiento topológico de los DAG se ejecuta en tiempo lineal, lo que permite que la planificación y la resolución de dependencias basadas en DAG sean eficientes desde el punto de vista computacional [2].

Los DAG proporcionan la base matemática para representar órdenes parciales: relaciones reflexivas, antisimétricas y transitivas. Todo conjunto finito parcialmente ordenado se corresponde con un DAG, y la relación de alcanzabilidad de un DAG define un orden parcial sobre sus vértices.

La terminología de los DAG tiene limitaciones en ámbitos donde los ciclos son características fundamentales en lugar de problemas que evitar. En los sistemas de retroalimentación, las redes neuronales recurrentes y muchos procesos biológicos, las relaciones circulares son esenciales. Los modelos causales basados en DAG también suponen relaciones estáticas y pueden tener dificultades para representar una causalidad que cambia con el tiempo o que funciona en ambos sentidos. La terminología puede resultar ambigua cuando se aplica a modelos gráficos probabilísticos cuyas aristas representan correlación en lugar de causalidad directa. Además, el orden topológico no es único: la mayoría de los DAG tienen varios órdenes válidos, lo que puede generar confusión sobre cuál es el «correcto» para una aplicación concreta.