En matemáticas , particularmente en teoría de grafos e informática , un gráfico acíclico dirigido ( DAG ) es un gráfico 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 gráfico dirigido es un DAG si y solo si se puede ordenar topológicamente , organizando los vértices como un orden lineal que sea consistente con todas las direcciones de los bordes. Los DAG tienen numerosas aplicaciones científicas y computacionales, que van desde la biología (evolución, árboles genealógicos, epidemiología) hasta las ciencias de la información (redes de citas) y la computación (programación).
Los gráficos acíclicos dirigidos a veces se denominan gráficos 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. Una ruta en un gráfico dirigido es una secuencia de aristas que tienen la propiedad de que el vértice final de cada arista de la secuencia es el mismo que el vértice inicial de la siguiente arista de la secuencia; un camino forma un ciclo si el vértice inicial de su primer borde es igual al vértice final de su último borde. Un gráfico acíclico dirigido es un gráfico 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 accesible desde sí mismo (por un camino con cero aristas). Si un vértice puede llegar a sí mismo a través de un camino no trivial (un camino con uno o más bordes), entonces ese camino es un ciclo, por lo que otra forma de definir grafos acíclicos dirigidos es que son los gráficos en los que ningún vértice puede llegar a sí mismo a través de un camino no trivial. [4]
La relación de accesibilidad 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 están ordenados como u ≤ v exactamente cuando existe una ruta dirigida de 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 accesibilidad 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 están ordenados como u ≤ v ≤ w .
El cierre transitivo de un DAG es el gráfico con más aristas que tiene la misma relación de accesibilidad 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 finito parcialmente ordenado ( S , ≤) , el gráfico que tiene un vértice para cada elemento de S y una arista para cada par de elementos en ≤ es automáticamente un DAG cerrado y tiene ( S , ≤) como relación de accesibilidad. De esta forma, todo conjunto finito parcialmente ordenado puede representarse como un DAG.
La reducción transitiva de un DAG es el gráfico con menos aristas que tiene la misma relación de accesibilidad 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 al descartar los bordes u → v para los cuales el DAG también contiene una ruta dirigida más larga de u a v . Al igual que el cierre transitivo, la reducción transitiva se define únicamente para los DAG. Por el contrario, para un gráfico dirigido que no es acíclico, puede haber más de un subgrafo mínimo con la misma relación de accesibilidad. [7] Las reducciones transitivas son útiles para visualizar los órdenes parciales que representan, porque tienen menos aristas que otros gráficos que representan los mismos órdenes y, por lo tanto, conducen a dibujos de gráficos más simples . Un diagrama de Hasse de orden parcial es un dibujo de la reducción transitiva en el que la orientación de cada arista se muestra 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 gráfico 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 gráfico que tiene un orden topológico no puede tener ciclos, porque el borde del primer vértice de un ciclo tendría que estar orientado de manera incorrecta. Por tanto, todo grafo con un orden topológico es acíclico. Por el contrario, todo grafo acíclico dirigido tiene al menos un ordenamiento topológico. Por lo tanto, la existencia de un ordenamiento topológico se puede utilizar como una definición equivalente de gráficos acíclicos dirigidos: son exactamente los gráficos que tienen ordenamientos topológicos. [2] En general, este orden no es único; un DAG tiene un orden topológico único si y solo si tiene una ruta dirigida que contiene todos los vértices, en cuyo caso el orden es el mismo que el orden en 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.
Robinson (1973) estudió el problema de enumeración de gráficos del conteo de gráficos acíclicos dirigidos. [11] El número de DAG en n vértices etiquetados, para n = 0, 1, 2, 3,… (sin restricciones en el orden en que aparecen estos números en un ordenamiento topológico del DAG) es
Estos números pueden calcularse mediante la relación de recurrencia
Eric W. Weisstein hizo conjeturas [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 automáticos , su matriz de adyacencia debe tener una diagonal cero, por lo que agregar I conserva la propiedad de que todos los coeficientes de la matriz son 0 o 1. [13]
Un árbol múltiple (también llamado gráfico fuertemente inequívoco o manglar ) es un DAG en el que hay como máximo una ruta dirigida entre dos vértices cualesquiera. De manera equivalente, es un DAG en el que el subgrafo accesible desde cualquier vértice induce un árbol no dirigido . [14]
Un poliárbol (también llamado árbol dirigido ) es un multiárbol formado orientando los bordes de un árbol no dirigido. [15]
Una arborescencia es un poliárbol formado al orientar los bordes de un árbol no dirigido lejos de un vértice particular, llamado raíz de la arborescencia.
La clasificación topológica es el problema algorítmico de encontrar un ordenamiento topológico de un DAG determinado. Se puede resolver en tiempo lineal . [16] El algoritmo de Kahn para la clasificación topológica construye la ordenación de los vértices directamente. Mantiene una lista de vértices que no tienen aristas entrantes de otros vértices que aún no se han incluido en el ordenamiento topológico parcialmente construido; Inicialmente, esta lista consta de vértices sin ninguna arista entrante. 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 finaliza cuando todos los vértices han sido procesados de esta manera. [17] Alternativamente, se puede construir un orden topológico invirtiendo una numeración de postorden de un recorrido de gráfico de búsqueda en profundidad . [dieciséis]
También es posible verificar si un gráfico dirigido dado es un DAG en tiempo lineal, ya sea intentando encontrar un orden topológico y luego probando para cada borde si el orden resultante es válido [18] o, alternativamente, para algunos algoritmos de ordenación topológica, verificando que el algoritmo ordena exitosamente todos los vértices sin cumplir una condición de error. [17]
Cualquier gráfico no dirigido se puede convertir en un DAG eligiendo un orden total para sus vértices y dirigiendo cada borde desde el punto final anterior en el orden hacia el punto final posterior. La orientación resultante de los bordes se llama orientación acíclica . Diferentes órdenes totales pueden conducir a la misma orientación acíclica, por lo que un gráfico 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 gráfico dado. [19]
Cualquier gráfico dirigido se puede convertir 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 es NP, difícil de encontrar. [20] Un gráfico dirigido arbitrario también se puede transformar en un DAG, llamado condensación , contrayendo cada uno de sus componentes fuertemente conectados en un solo supervértice. [21] Cuando el gráfico 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 gráfico mismo.
El cierre transitivo de un DAG determinado, con n vértices y m aristas, se puede construir en el 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 el tiempo O ( n ω ) donde ω < 2,373 es el exponente de los algoritmos de multiplicación de matrices ; ésta 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 a los que se puede acceder mediante al menos un camino de longitud dos o más de pares que sólo pueden conectarse mediante un camino de longitud uno. La reducción transitiva consta de 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 la clausura transitiva. [24]
El problema de cierre toma como entrada un gráfico acíclico dirigido ponderado por vértices y busca el peso mínimo (o máximo) de un cierre: un conjunto de vértices C , tal 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 equivale al mismo problema sobre la condensación del grafo. Puede resolverse en tiempo polinómico utilizando un problema de reducción al flujo máximo . [25]
Algunos algoritmos se vuelven más simples cuando se usan en DAG en lugar de gráficos generales, basándose en el principio de ordenamiento topológico. Por ejemplo, es posible encontrar las rutas más cortas y las rutas más largas desde un vértice inicial determinado en DAG en tiempo lineal procesando los vértices en un orden topológico y calculando la longitud de la ruta para cada vértice como la longitud mínima o máxima obtenida a través de cualquier de sus bordes entrantes. [26] Por el contrario, para gráficos arbitrarios, el camino más corto puede requerir algoritmos más lentos, como el algoritmo de Dijkstra o el algoritmo de Bellman-Ford , [27] y los caminos más largos en gráficos arbitrarios son NP-difíciles de encontrar. [28]
Las representaciones de gráficos acíclicos dirigidos de pedidos parciales tienen muchas aplicaciones en la programación de sistemas de tareas con restricciones de pedido. [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 ha sido modificada, o los archivos objeto de un software de computadora después de su fuente. El código ha sido cambiado. En este contexto, un gráfico de dependencia es un gráfico que tiene un vértice para cada objeto que se actualizará y un borde que conecta dos objetos siempre que uno de ellos deba actualizarse antes que el otro. Un ciclo en este gráfico se denomina dependencia circular y generalmente no está permitido porque no habría forma de programar de manera consistente las tareas involucradas en el ciclo. Los gráficos de dependencia sin dependencias circulares forman DAG. [30]
Por ejemplo, cuando cambia una celda de una hoja de cálculo , es necesario volver a calcular los valores de otras celdas que dependen directa o indirectamente de la celda modificada. Para este problema, las tareas a 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 usa 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 utilizar este orden topológico para programar las actualizaciones de las celdas permite actualizar toda la hoja de cálculo con una sola evaluación por celda. [31] Problemas similares de ordenación 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 restricciones de programación basada en DAG . En este método, los vértices de un DAG representan hitos de un proyecto en lugar de tareas específicas a realizar. En cambio, una tarea o actividad está representada por 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. La ruta más larga en este DAG representa la ruta crítica del proyecto, la que controla el tiempo total del proyecto. Se pueden programar hitos individuales según la longitud 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 ingresan a un elemento de procesamiento a través de sus bordes entrantes y salen del elemento a través de sus bordes salientes.
Por ejemplo, en el diseño de circuitos electrónicos, los bloques lógicos combinacionales estáticos se pueden representar 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í no son necesariamente acíclicos o dirigidos.
Los lenguajes de programación de flujo de datos describen sistemas de operaciones en 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 se realiza mediante 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 declaraciones sin bucles ni ramas 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 feedforward son otro ejemplo.
Los grafos en los que los vértices representan eventos que ocurren en un tiempo definido, y donde las aristas siempre apuntan desde el vértice temprano a un vértice 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 se sigue cualquier camino en el gráfico, por lo que nunca se puede regresar a un vértice en un camino. Esto refleja nuestra intuición natural de que la causalidad significa que los eventos sólo 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 de la gravedad cuántica, aunque en este caso los gráficos considerados son transitivamente completos. En el siguiente ejemplo del historial de versiones, cada versión del software está asociada a una hora única, normalmente la hora en la que se guardó, confirmó o lanzó la versión. En los ejemplos de gráficos de citas a continuación, los documentos se publican al mismo tiempo 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 representen relaciones causales entre los eventos, tendremos un gráfico acíclico dirigido. [38] Por ejemplo, una red bayesiana representa un sistema de eventos probabilísticos como vértices en un gráfico 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 gráfico moral de un DAG es el gráfico no dirigido creado agregando un borde (no dirigido) entre todos los padres del mismo vértice (a veces llamado casarse ), y luego reemplazando todos los bordes dirigidos por bordes no dirigidos. [40] Otro tipo de gráfico 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 utilizan a menudo para estimar el valor esperado de diferentes opciones de intervención. [42] [43]
Lo contrario también es cierto. Es decir, en cualquier aplicación representada por un gráfico acíclico dirigido hay una estructura causal, ya sea un orden o tiempo explícito en el ejemplo o un orden que puede derivarse de la estructura del gráfico. Esto se debe a que todos los grafos acíclicos dirigidos tienen un orden topológico, es decir, hay al menos una manera de poner 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 gráficos acíclicos dirigidos, con un vértice para cada miembro de la familia y una arista para cada relación padre-hijo. [44] A pesar del nombre, estos gráficos no son necesariamente árboles debido a la posibilidad de que los matrimonios entre parientes (por lo que un niño tiene un ancestro común tanto por parte de la madre como del padre) provoquen un colapso del pedigrí . [45] Los gráficos de ascendencia matrilineal (relaciones madre-hija) y de ascendencia patrilineal (relaciones padre-hijo) son árboles dentro de este gráfico. Como 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 revisiones 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 un borde que conecta pares de revisiones que se derivaron directamente entre sí. Estos no son árboles en general debido a 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 en el transcurso 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 "inversión" que reemplazan pares de triángulos por un par de triángulos diferente. El DAG histórico de este algoritmo tiene un vértice para cada triángulo construido como parte del algoritmo y bordes de cada triángulo a los otros dos o tres triángulos que lo reemplazan. Esta estructura permite responder de manera eficiente a las consultas de ubicación de puntos : para encontrar la ubicación de un punto de consulta q en la triangulación de Delaunay, siga una ruta en el historial DAG, moviéndose en cada paso al triángulo de reemplazo que contiene q . El último triángulo alcanzado en este camino 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 produjo el primer modelo de red de citas, el modelo Price . [50] En este caso, el recuento de citas de un artículo es solo 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 proporcionan otro ejemplo en el que los jueces sustentan sus conclusiones en un caso recordando otras decisiones tomadas en casos anteriores. Un último ejemplo lo proporcionan 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 redes de citas con técnicas que no están disponibles al analizar los gráficos generales considerados en muchos estudios que utilizan el análisis de redes . Por ejemplo, la reducción transitiva brinda nuevos conocimientos sobre las distribuciones de citas que se encuentran en diferentes aplicaciones, destacando diferencias claras en los mecanismos que crean redes de citas en diferentes contextos. [51] Otra técnica es el análisis de 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. Muchos de ellos 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 de la ruta más larga, desde el enésimo nodo agregado a la red hasta el primer nodo de la red, escala como [52] .
Los gráficos acíclicos dirigidos también se pueden utilizar como una representación compacta de una colección de secuencias. En este tipo de aplicación, se encuentra un DAG en el que las rutas forman las secuencias dadas. Cuando muchas de las secuencias comparten las mismas subsecuencias, estas subsecuencias compartidas se pueden representar 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 gráfico de palabras acíclico dirigido es una estructura de datos en informática formada por un gráfico acíclico dirigido con una única fuente y con aristas etiquetadas por letras o símbolos; Las rutas desde la fuente hasta los sumideros en este gráfico representan un conjunto de cadenas , como palabras en inglés. [53] Cualquier conjunto de secuencias se puede representar 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 pueda representar mediante un solo vértice de árbol. [54]
La misma idea de usar un DAG para representar una familia de rutas 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 arista están etiquetados con un 0 o un 1. El valor de la función para cualquier asignación de verdad a las variables es el valor en el sumidero encontrado siguiendo una ruta, comenzando desde el único vértice de origen, que en cada vértice no 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 binarios pueden verse como formas comprimidas de árboles de decisión que ahorran espacio al permitir que las rutas se vuelvan a unir cuando coinciden en los resultados de todas las decisiones restantes. [57]
