En matemáticas , particularmente en teoría de grafos y ciencias de la computación , un grafo acíclico dirigido ( DAG ) es un grafo dirigido sin ciclos dirigidos . Es decir, consta de vértices y aristas (también llamados arcos ), con cada arista dirigida de un vértice a otro, de modo que seguir esas direcciones nunca formará un bucle cerrado. Un grafo dirigido es un DAG si y solo si se puede ordenar topológicamente , al disponer los vértices como un ordenamiento lineal que sea consistente con todas las direcciones de las aristas. Los DAG tienen numerosas aplicaciones científicas y computacionales, que van desde la biología (evolución, árboles genealógicos, epidemiología) hasta la ciencia de la información (redes de citas) y la computación (programación).
Los grafos acíclicos dirigidos también se denominan grafos dirigidos acíclicos [1] o dígrafos acíclicos . [2]
Un grafo está formado por vértices y por aristas que conectan pares de vértices, donde los vértices pueden ser cualquier tipo de objeto que esté conectado en pares por aristas. En el caso de un grafo dirigido , cada arista tiene una orientación, de un vértice a otro vértice. Un camino en un grafo dirigido es una secuencia de aristas que tiene la propiedad de que el vértice final de cada arista en la secuencia es el mismo que el vértice inicial de la siguiente arista en la secuencia; un camino forma un ciclo si el vértice inicial de su primera arista es igual al vértice final de su última arista. Un grafo acíclico dirigido es un grafo dirigido que no tiene ciclos. [1] [2] [3]
Se dice que un vértice v de un grafo dirigido es alcanzable desde otro vértice u cuando existe un camino que comienza en u y termina en v . Como caso especial, se considera que cada vértice es alcanzable desde sí mismo (por un camino con cero aristas). Si un vértice puede alcanzarse a sí mismo a través de un camino no trivial (un camino con una o más aristas), entonces ese camino es un ciclo, por lo que otra forma de definir los grafos acíclicos dirigidos es que son los grafos en los que ningún vértice puede alcanzarse a sí mismo a través de un camino no trivial. [4]
La relación de alcanzabilidad de un DAG se puede formalizar como un orden parcial ≤ en los vértices del DAG. En este orden parcial, dos vértices u y v se ordenan como u ≤ v exactamente cuando existe un camino dirigido desde u a v en el DAG; es decir, cuando u puede alcanzar v (o v es alcanzable desde u ). [5] Sin embargo, diferentes DAG pueden dar lugar a la misma relación de alcanzabilidad y al mismo orden parcial. [6] Por ejemplo, un DAG con dos aristas u → v y v → w tiene la misma relación de alcanzabilidad que el DAG con tres aristas u → v , v → w y u → w . Ambos DAG producen el mismo orden parcial, en el que los vértices se ordenan como u ≤ v ≤ w .
El cierre transitivo de un DAG es el grafo con más aristas que tiene la misma relación de alcanzabilidad que el DAG. Tiene una arista u → v para cada par de vértices ( u , v ) en la relación de alcanzabilidad ≤ del DAG, y por lo tanto puede considerarse como una traducción directa de la relación de alcanzabilidad ≤ en términos de teoría de grafos. El mismo método de traducir órdenes parciales en DAG funciona de manera más general: para cada conjunto parcialmente ordenado finito ( S , ≤) , el grafo que tiene un vértice para cada elemento de S y una arista para cada par de elementos en ≤ es automáticamente un DAG transitivamente cerrado, y tiene ( S , ≤) como su relación de alcanzabilidad. De esta manera, cada conjunto parcialmente ordenado finito puede representarse como un DAG.
La reducción transitiva de un DAG es el grafo con menos aristas que tiene la misma relación de alcanzabilidad que el DAG. Tiene una arista u → v para cada par de vértices ( u , v ) en la relación de cobertura de la relación de alcanzabilidad ≤ del DAG. Es un subgrafo del DAG, formado descartando las aristas u → v para las cuales el DAG también contiene un camino dirigido más largo de u a v . Al igual que el cierre transitivo, la reducción transitiva se define de forma única para los DAG. Por el contrario, para un grafo dirigido que no es acíclico, puede haber más de un subgrafo mínimo con la misma relación de alcanzabilidad. [7] Las reducciones transitivas son útiles para visualizar los órdenes parciales que representan, porque tienen menos aristas que otros grafos que representan los mismos órdenes y, por lo tanto, conducen a dibujos de grafos más simples . Un diagrama de Hasse de un orden parcial es un dibujo de la reducción transitiva en el que se muestra la orientación de cada arista colocando el vértice inicial de la arista en una posición más baja que su vértice final. [8]
Un ordenamiento topológico de un grafo dirigido es un ordenamiento de sus vértices en una secuencia, de modo que para cada arista el vértice inicial de la arista ocurre antes en la secuencia que el vértice final de la arista. Un grafo que tiene un ordenamiento topológico no puede tener ciclos, porque la arista en el vértice más temprano de un ciclo tendría que estar orientada de manera incorrecta. Por lo tanto, todo grafo con un ordenamiento topológico es acíclico. A la inversa, todo grafo acíclico dirigido tiene al menos un ordenamiento topológico. Por lo tanto, la existencia de un ordenamiento topológico puede usarse como una definición equivalente de un grafo acíclico dirigido: son exactamente los grafos que tienen ordenamientos topológicos. [2] En general, este ordenamiento no es único; un DAG tiene un ordenamiento topológico único si y solo si tiene una ruta dirigida que contiene todos los vértices, en cuyo caso el ordenamiento es el mismo que el orden en el que aparecen los vértices en la ruta. [9]
La familia de ordenamientos topológicos de un DAG es la misma que la familia de extensiones lineales de la relación de alcanzabilidad para el DAG, [10] por lo que dos gráficos cualesquiera que representen el mismo orden parcial tienen el mismo conjunto de órdenes topológicos.
El problema de enumeración de grafos de contar grafos acíclicos dirigidos fue estudiado por Robinson (1973). [11] El número de DAG en n vértices etiquetados, para n = 0, 1, 2, 3, … (sin restricciones en el orden en el que estos números aparecen en un ordenamiento topológico del DAG) es
Estos números pueden calcularse mediante la relación de recurrencia
Eric W. Weisstein conjeturó, [12] y McKay et al. (2004) demostraron, que los mismos números cuentan las matrices (0,1) para las cuales todos los valores propios son números reales positivos . La prueba es biyectiva : una matriz A es una matriz de adyacencia de un DAG si y solo si A + I es una matriz (0,1) con todos los valores propios positivos, donde I denota la matriz identidad . Debido a que un DAG no puede tener bucles propios , su matriz de adyacencia debe tener una diagonal cero, por lo que agregar I preserva la propiedad de que todos los coeficientes de la matriz son 0 o 1. [13]
Un multiárbol (también llamado grafo fuertemente inequívoco o manglar ) es un DAG en el que hay como máximo un camino dirigido entre dos vértices cualesquiera. De manera equivalente, es un DAG en el que el subgrafo al que se puede llegar desde cualquier vértice induce un árbol no dirigido . [14]
Un poliárbol (también llamado árbol dirigido ) es un multiárbol formado al orientar los bordes de un árbol no dirigido. [15]
Una arborescencia es un poliárbol formado orientando los bordes de un árbol no dirigido lejos de un vértice particular, llamado raíz de la arborescencia.
La ordenación topológica es el problema algorítmico de encontrar un ordenamiento topológico de un DAG dado. Se puede resolver en tiempo lineal . [16] El algoritmo de Kahn para la ordenación topológica construye el ordenamiento de vértices directamente. Mantiene una lista de vértices que no tienen aristas entrantes de otros vértices que no se han incluido ya en el ordenamiento topológico parcialmente construido; inicialmente esta lista consta de los vértices sin aristas entrantes en absoluto. Luego, agrega repetidamente un vértice de esta lista al final del ordenamiento topológico parcialmente construido y verifica si sus vecinos deben agregarse a la lista. El algoritmo termina cuando todos los vértices se han procesado de esta manera. [17] Alternativamente, se puede construir un ordenamiento topológico invirtiendo una numeración de posorden de un recorrido de grafo de búsqueda en profundidad . [16]
También es posible verificar si un gráfico dirigido dado es un DAG en tiempo lineal, ya sea intentando encontrar un ordenamiento topológico y luego probando para cada borde si el ordenamiento resultante es válido [18] o alternativamente, para algunos algoritmos de ordenamiento topológico, verificando que el algoritmo ordena exitosamente todos los vértices sin cumplir una condición de error. [17]
Cualquier grafo no dirigido puede convertirse en un DAG eligiendo un orden total para sus vértices y dirigiendo cada arista desde el punto final anterior en el orden hasta el punto final posterior. La orientación resultante de las aristas se denomina orientación acíclica . Diferentes órdenes totales pueden conducir a la misma orientación acíclica, por lo que un grafo de n vértices puede tener menos de n ! orientaciones acíclicas. El número de orientaciones acíclicas es igual a | χ (−1)| , donde χ es el polinomio cromático del grafo dado. [19]
Cualquier grafo dirigido puede convertirse en un DAG eliminando un conjunto de vértices de retroalimentación o un conjunto de arcos de retroalimentación , un conjunto de vértices o aristas (respectivamente) que toca todos los ciclos. Sin embargo, el conjunto más pequeño de estos es NP-difícil de encontrar. [20] Un grafo dirigido arbitrario también puede transformarse en un DAG, llamado su condensación , contrayendo cada uno de sus componentes fuertemente conectados en un solo supervértice. [21] Cuando el grafo ya es acíclico, sus conjuntos de vértices de retroalimentación y arcos de retroalimentación más pequeños están vacíos , y su condensación es el grafo mismo.
El cierre transitivo de un DAG dado, con n vértices y m aristas, se puede construir en tiempo O ( mn ) utilizando una búsqueda en amplitud o en profundidad para probar la accesibilidad desde cada vértice. [22] Alternativamente, se puede resolver en tiempo O ( n ω ) donde ω < 2.373 es el exponente para algoritmos de multiplicación de matrices ; esto es una mejora teórica sobre el límite O ( mn ) para gráficos densos . [23]
En todos estos algoritmos de cierre transitivo, es posible distinguir pares de vértices que son alcanzables por al menos un camino de longitud dos o más de pares que solo pueden conectarse por un camino de longitud uno. La reducción transitiva consiste en las aristas que forman caminos de longitud uno que son los únicos caminos que conectan sus puntos finales. Por lo tanto, la reducción transitiva se puede construir en los mismos límites de tiempo asintóticos que el cierre transitivo. [24]
El problema de clausura toma como entrada un grafo acíclico dirigido ponderado por vértices y busca el peso mínimo (o máximo) de una clausura – un conjunto de vértices C , de modo que ninguna arista salga de C . El problema puede formularse para grafos dirigidos sin el supuesto de aciclicidad, pero sin mayor generalidad, porque en este caso es equivalente al mismo problema en la condensación del grafo. Puede resolverse en tiempo polinomial utilizando una reducción al problema de flujo máximo . [25]
Algunos algoritmos se vuelven más simples cuando se utilizan en DAG en lugar de grafos generales, basándose en el principio de ordenamiento topológico. Por ejemplo, es posible encontrar los caminos más cortos y más largos desde un vértice inicial dado en DAG en tiempo lineal procesando los vértices en un orden topológico y calculando la longitud del camino para cada vértice como la longitud mínima o máxima obtenida a través de cualquiera de sus aristas entrantes. [26] Por el contrario, para grafos arbitrarios el camino más corto puede requerir algoritmos más lentos como el algoritmo de Dijkstra o el algoritmo Bellman–Ford , [27] y los caminos más largos en grafos arbitrarios son NP-difíciles de encontrar. [28]
Las representaciones de grafos acíclicos dirigidos de ordenamientos parciales tienen muchas aplicaciones en la programación de sistemas de tareas con restricciones de ordenamiento. [29] Una clase importante de problemas de este tipo se refiere a colecciones de objetos que necesitan ser actualizados, como las celdas de una hoja de cálculo después de que una de las celdas haya sido cambiada, o los archivos de objetos de un software de computadora después de que su código fuente haya sido cambiado. En este contexto, un grafo de dependencia es un grafo que tiene un vértice para cada objeto que se va a actualizar, y una arista que conecta dos objetos siempre que uno de ellos necesite ser actualizado antes que el otro. Un ciclo en este grafo se llama dependencia circular , y generalmente no se permite, porque no habría manera de programar consistentemente las tareas involucradas en el ciclo. Los grafos de dependencia sin dependencias circulares forman DAG. [30]
Por ejemplo, cuando cambia una celda de una hoja de cálculo , es necesario recalcular los valores de otras celdas que dependen directa o indirectamente de la celda modificada. Para este problema, las tareas que se deben programar son los recálculos de los valores de celdas individuales de la hoja de cálculo. Las dependencias surgen cuando una expresión en una celda utiliza un valor de otra celda. En tal caso, el valor que se utiliza debe recalcularse antes que la expresión que lo utiliza. Ordenar topológicamente el gráfico de dependencia y usar este orden topológico para programar las actualizaciones de celdas permite actualizar toda la hoja de cálculo con una sola evaluación por celda. [31] Problemas similares de ordenamiento de tareas surgen en los archivos make para la compilación de programas [31] y la programación de instrucciones para la optimización de programas informáticos de bajo nivel. [32]
La técnica de evaluación y revisión de programas (PERT), un método para la gestión de grandes proyectos humanos que fue una de las primeras aplicaciones de los DAG, utiliza una formulación algo diferente de las restricciones de programación basadas en DAG. En este método, los vértices de un DAG representan hitos de un proyecto en lugar de tareas específicas que se deben realizar. En cambio, una tarea o actividad se representa mediante un borde de un DAG, que conecta dos hitos que marcan el comienzo y la finalización de la tarea. Cada uno de estos bordes está etiquetado con una estimación de la cantidad de tiempo que le tomará a un equipo de trabajadores realizar la tarea. El camino más largo en este DAG representa el camino crítico del proyecto, el que controla el tiempo total del proyecto. Los hitos individuales se pueden programar de acuerdo con las longitudes de los caminos más largos que terminan en sus vértices. [33]
Se puede utilizar un gráfico acíclico dirigido para representar una red de elementos de procesamiento. En esta representación, los datos entran en un elemento de procesamiento a través de sus bordes de entrada y salen del elemento a través de sus bordes de salida.
Por ejemplo, en el diseño de circuitos electrónicos, los bloques lógicos combinacionales estáticos pueden representarse como un sistema acíclico de puertas lógicas que calcula una función de una entrada, donde la entrada y la salida de la función se representan como bits individuales . En general, la salida de estos bloques no se puede utilizar como entrada a menos que sea capturada por un registro o elemento de estado que mantenga sus propiedades acíclicas. [34] Los esquemas de circuitos electrónicos, ya sea en papel o en una base de datos, son una forma de gráficos acíclicos dirigidos que utilizan instancias o componentes para formar una referencia dirigida a un componente de nivel inferior. Los circuitos electrónicos en sí mismos no son necesariamente acíclicos o dirigidos.
Los lenguajes de programación de flujo de datos describen sistemas de operaciones sobre flujos de datos y las conexiones entre las salidas de algunas operaciones y las entradas de otras. Estos lenguajes pueden ser convenientes para describir tareas repetitivas de procesamiento de datos, en las que la misma colección de operaciones conectadas acíclicamente se aplica a muchos elementos de datos. Se pueden ejecutar como un algoritmo paralelo en el que cada operación es realizada por un proceso paralelo tan pronto como otro conjunto de entradas está disponible para él. [35]
En los compiladores , el código de línea recta (es decir, secuencias de instrucciones sin bucles ni ramificaciones condicionales) puede representarse mediante un DAG que describe las entradas y salidas de cada una de las operaciones aritméticas realizadas dentro del código. Esta representación permite al compilador realizar la eliminación de subexpresiones comunes de manera eficiente. [36] En un nivel superior de organización del código, el principio de dependencias acíclicas establece que las dependencias entre módulos o componentes de un sistema de software grande deben formar un gráfico acíclico dirigido. [37]
Las redes neuronales de propagación hacia adelante son otro ejemplo.
Los gráficos en los que los vértices representan eventos que ocurren en un tiempo definido, y donde las aristas siempre apuntan desde el vértice de tiempo temprano a un vértice de tiempo tardío de la arista, son necesariamente dirigidos y acíclicos. La falta de un ciclo se debe a que el tiempo asociado con un vértice siempre aumenta a medida que sigues cualquier camino en el gráfico, por lo que nunca puedes regresar a un vértice en un camino. Esto refleja nuestra intuición natural de que la causalidad significa que los eventos solo pueden afectar el futuro, nunca afectan el pasado y, por lo tanto, no tenemos bucles causales . Un ejemplo de este tipo de gráfico acíclico dirigido son los que se encuentran en el enfoque de conjunto causal para la gravedad cuántica , aunque en este caso los gráficos considerados son transitivamente completos. En el ejemplo de historial de versiones a continuación, cada versión del software está asociada con un tiempo único, generalmente el momento en que se guardó, confirmó o lanzó la versión. En los ejemplos de gráficos de citas a continuación, los documentos se publican a la vez y solo pueden hacer referencia a documentos más antiguos.
A veces los eventos no están asociados con un tiempo físico específico. Siempre que los pares de eventos tengan una relación puramente causal, es decir, los bordes representan relaciones causales entre los eventos, tendremos un grafo acíclico dirigido. [38] Por ejemplo, una red bayesiana representa un sistema de eventos probabilísticos como vértices en un grafo acíclico dirigido, en el que la probabilidad de un evento puede calcularse a partir de las probabilidades de sus predecesores en el DAG. [39] En este contexto, el grafo moral de un DAG es el grafo no dirigido creado agregando un borde (no dirigido) entre todos los padres del mismo vértice (a veces llamado casamiento ), y luego reemplazando todos los bordes dirigidos por bordes no dirigidos. [40] Otro tipo de grafo con una estructura causal similar es un diagrama de influencia , cuyos vértices representan decisiones a tomar o información desconocida, y cuyos bordes representan influencias causales de un vértice a otro. [41] En epidemiología , por ejemplo, estos diagramas se usan a menudo para estimar el valor esperado de diferentes opciones de intervención. [42] [43]
Lo inverso también es cierto. Es decir, en cualquier aplicación representada por un grafo acíclico dirigido existe una estructura causal, ya sea un orden explícito o temporal en el ejemplo o un orden que se puede derivar de la estructura del grafo. Esto se debe a que todos los grafos acíclicos dirigidos tienen un orden topológico, es decir, hay al menos una forma de colocar los vértices en un orden tal que todas las aristas apunten en la misma dirección a lo largo de ese orden.
Los árboles genealógicos pueden verse como grafos acíclicos dirigidos, con un vértice para cada miembro de la familia y un borde para cada relación padre-hijo. [44] A pesar del nombre, estos grafos no son necesariamente árboles debido a la posibilidad de que los matrimonios entre parientes (por lo que un niño tiene un antepasado común tanto por el lado materno como por el paterno) provoquen un colapso del pedigrí . [45] Los grafos de descendencia matrilineal (relaciones madre-hija) y de descendencia patrilineal (relaciones padre-hijo) son árboles dentro de este grafo. Debido a que nadie puede convertirse en su propio antepasado, los árboles genealógicos son acíclicos. [46]
El historial de versiones de un sistema de control de versiones distribuido , como Git , generalmente tiene la estructura de un gráfico acíclico dirigido, en el que hay un vértice para cada revisión y una arista que conecta pares de revisiones que se derivaron directamente entre sí. Estos no son árboles en general debido a las fusiones. [47]
En muchos algoritmos aleatorios en geometría computacional , el algoritmo mantiene un DAG histórico que representa el historial de versiones de una estructura geométrica a lo largo de una secuencia de cambios en la estructura. Por ejemplo, en un algoritmo incremental aleatorio para la triangulación de Delaunay , la triangulación cambia reemplazando un triángulo por tres triángulos más pequeños cuando se agrega cada punto, y mediante operaciones de "volteo" que reemplazan pares de triángulos por un par de triángulos diferente. El DAG histórico para este algoritmo tiene un vértice para cada triángulo construido como parte del algoritmo, y aristas desde cada triángulo hasta los otros dos o tres triángulos que lo reemplazan. Esta estructura permite que las consultas de ubicación de puntos se respondan de manera eficiente: para encontrar la ubicación de un punto de consulta q en la triangulación de Delaunay, siga una ruta en el DAG histórico, en cada paso moviéndose al triángulo de reemplazo que contiene q . El triángulo final alcanzado en esta ruta debe ser el triángulo de Delaunay que contiene q . [48]
En un gráfico de citas, los vértices son documentos con una única fecha de publicación. Los bordes representan las citas de la bibliografía de un documento a otros documentos necesariamente anteriores. El ejemplo clásico proviene de las citas entre artículos académicos, como se señala en el artículo de 1965 "Networks of Scientific Papers" [49] de Derek J. de Solla Price, quien luego produjo el primer modelo de una red de citas, el modelo de Price . [50] En este caso, el recuento de citas de un artículo es simplemente el grado de entrada del vértice correspondiente de la red de citas. Esta es una medida importante en el análisis de citas . Las sentencias judiciales brindan otro ejemplo, ya que los jueces respaldan sus conclusiones en un caso recordando otras decisiones anteriores tomadas en casos anteriores. Un ejemplo final lo brindan las patentes que deben hacer referencia a la técnica anterior , patentes anteriores que son relevantes para la reivindicación de patente actual. Al tener en cuenta las propiedades especiales de los gráficos acíclicos dirigidos, se pueden analizar las redes de citas con técnicas que no están disponibles cuando se analizan los gráficos generales considerados en muchos estudios que utilizan el análisis de redes . Por ejemplo, la reducción transitiva proporciona nuevos conocimientos sobre las distribuciones de citas encontradas en diferentes aplicaciones, destacando claras diferencias en los mecanismos que crean redes de citas en diferentes contextos. [51] Otra técnica es el análisis de la ruta principal , que rastrea los enlaces de citas y sugiere las cadenas de citas más significativas en un gráfico de citas determinado .
El modelo de Price es demasiado simple para ser un modelo realista de una red de citas , pero es lo suficientemente simple como para permitir soluciones analíticas para algunas de sus propiedades. Muchas de ellas se pueden encontrar utilizando resultados derivados de la versión no dirigida del modelo de Price , el modelo de Barabási–Albert . Sin embargo, dado que el modelo de Price proporciona un gráfico acíclico dirigido, es un modelo útil cuando se buscan cálculos analíticos de propiedades exclusivas de los gráficos acíclicos dirigidos. Por ejemplo, la longitud del camino más largo, desde el n-ésimo nodo agregado a la red hasta el primer nodo de la red, escala como [52] .
Los grafos acíclicos dirigidos también pueden utilizarse como una representación compacta de una colección de secuencias. En este tipo de aplicación, se encuentra un DAG en el que los caminos forman las secuencias dadas. Cuando muchas de las secuencias comparten las mismas subsecuencias, estas subsecuencias compartidas pueden representarse mediante una parte compartida del DAG, lo que permite que la representación utilice menos espacio del que se necesitaría para enumerar todas las secuencias por separado. Por ejemplo, el grafo de palabras acíclico dirigido es una estructura de datos en informática formada por un grafo acíclico dirigido con una única fuente y con aristas etiquetadas con letras o símbolos; los caminos desde la fuente hasta los sumideros en este grafo representan un conjunto de cadenas , como palabras en inglés. [53] Cualquier conjunto de secuencias puede representarse como caminos en un árbol, formando un vértice de árbol para cada prefijo de una secuencia y haciendo que el padre de uno de estos vértices represente la secuencia con un elemento menos; el árbol formado de esta manera para un conjunto de cadenas se llama trie . Un gráfico de palabras acíclico dirigido ahorra espacio en un trie al permitir que los caminos diverjan y se vuelvan a unir, de modo que un conjunto de palabras con los mismos sufijos posibles se puede representar mediante un único vértice de árbol. [54]
La misma idea de usar un DAG para representar una familia de caminos ocurre en el diagrama de decisión binaria , [55] [56] una estructura de datos basada en DAG para representar funciones binarias. En un diagrama de decisión binaria, cada vértice que no es sumidero está etiquetado con el nombre de una variable binaria, y cada sumidero y cada borde están etiquetados con un 0 o 1. El valor de la función para cualquier asignación de verdad a las variables es el valor en el sumidero encontrado al seguir un camino, comenzando desde el vértice de origen único, que en cada vértice que no es sumidero sigue el borde saliente etiquetado con el valor de la variable de ese vértice. Así como los gráficos de palabras acíclicos dirigidos pueden verse como una forma comprimida de intentos, los diagramas de decisión binaria pueden verse como formas comprimidas de árboles de decisión que ahorran espacio al permitir que los caminos se vuelvan a unir cuando coinciden en los resultados de todas las decisiones restantes. [57]
