Gráfico Acíclico Dirigido - Directed acyclic graph
En las matemáticas , en particular la teoría de grafos , y la informática , un gráfico acíclico dirigido ( DAG o dag / d æ ɡ / ( escuchar )
) es un gráfico dirigido con no hay 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 la sociología (redes de citas) y la computación (programación).
Definiciones
Un gráfico está formado por vértices y 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 gráfico dirigido , cada borde tiene una orientación, de un vértice a otro vértice. Un camino en un gráfico 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 del siguiente arista en 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.
Se dice que un vértice v de una gráfica dirigida es accesible desde otro vértice u cuando existe una ruta que comienza en u y termina en v . Como caso especial, se considera que cada vértice es accesible desde sí mismo (por una ruta con cero aristas). Si un vértice puede alcanzarse a sí mismo a través de una ruta no trivial (una ruta con uno o más bordes), entonces esa ruta es un ciclo, por lo que otra forma de definir gráficos 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.
Propiedades matematicas
Accesibilidad, cierre transitivo y reducción transitiva
La relación de accesibilidad en cualquier grafo acíclico dirigido 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 clasificadas como u ≤ v exactamente cuando existe un camino dirigido desde u a v en el DAG; es decir, cuando v es accesible desde u . Sin embargo, diferentes DAG pueden dar lugar a la misma relación de accesibilidad y al mismo orden parcial. Por ejemplo, el DAG con dos bordes un → b y b → c tiene la misma relación de alcanzabilidad como la gráfica con tres bordes un → b , b → c , y un → c . Ambos DAGS producen el mismo orden parcial, en el que los vértices se ordenan como a ≤ b ≤ c .
Si G es un DAG, su cierre transitivo es el gráfico con más aristas que representa la misma relación de accesibilidad. Tiene un borde u → v siempre que u puede alcanzar v . Es decir, tiene un borde para cada par relacionado u ≤ v de elementos distintos en la relación de accesibilidad de G y, por lo tanto, puede pensarse como una traducción directa de la relación de accesibilidad ≤ en términos de teoría de gráficos. 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 miembro de S y un borde para cada par de elementos relacionados por u ≤ v es automáticamente un DAG cerrado transitivamente, y tiene ( S , ≤) como su relación de accesibilidad. De esta manera, cada conjunto finito parcialmente ordenado puede representarse como la relación de accesibilidad de un DAG.
La reducción transitiva de un DAG G es la gráfica con los bordes menor número que representa la misma relación de alcanzabilidad como G . Es un subgrafo de G , formado descartando las aristas u → v para las cuales G también contiene un camino más largo que conecta los mismos dos vértices. Al igual que el cierre transitivo, la reducción transitiva se define de forma única para los DAG. Por el contrario, para un gráfico dirigido que no es acíclico, puede haber más de un subgráfico mínimo con la misma relación de accesibilidad.
Si un DAG G tiene una relación de accesibilidad descrita por el orden parcial ≤ , entonces la reducción transitiva de G es un subgrafo de G que tiene un borde u → v para cada par en la relación de cobertura de ≤ . Las reducciones transitivas son útiles para visualizar los órdenes parciales que representan, porque tienen menos bordes 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 borde se muestra colocando el vértice inicial del borde en una posición más baja que su vértice final.
Orden topológico
Un ordenamiento topológico de un grafo dirigido es un ordenamiento de sus vértices en una secuencia, de modo que para cada borde, el vértice inicial del borde ocurre antes en la secuencia que el vértice final del borde. Un gráfico que tiene un orden topológico no puede tener ciclos, porque el borde en el vértice más temprano de un ciclo tendría que estar orientado de manera incorrecta. Por tanto, todo gráfico con un orden topológico es acíclico. Por el contrario, cada grafo acíclico dirigido tiene al menos un orden topológico. Por tanto, la existencia de un ordenamiento topológico se puede utilizar como una definición equivalente de un gráfico acíclico dirigido: son exactamente los gráficos que tienen ordenamientos topológicos. 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 el que aparecen los vértices en la ruta.
La familia de ordenamientos topológicos de un DAG es la misma que la familia de extensiones lineales de la relación de accesibilidad para el DAG, por lo que dos gráficos que representan el mismo orden parcial tienen el mismo conjunto de órdenes topológicos.
Enumeración combinatoria
El gráfico enumeración problema de contar gráficos acíclicos dirigidos fue estudiada por Robinson (1973) . 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 orden topológico del DAG) es
Estos números pueden calcularse mediante la relación de recurrencia
Eric W. Weisstein conjeturó, y McKay et al. (2004) demostró que los mismos números cuentan las matrices (0,1) para las que 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 conserva la propiedad de que todos los coeficientes de la matriz son 0 o 1.
Familias relacionadas de gráficos
Un polytree es un gráfico dirigido que se forma al orientar los bordes de un árbol libre . Cada polytree es un DAG. En particular, esto es cierto para las arborescencias que se forman al dirigir todos los bordes hacia afuera desde las raíces de un árbol.
Un árbol múltiple (también llamado gráfico claramente inequívoco o manglar) es un gráfico dirigido en el que hay como máximo una ruta dirigida (en cualquier dirección) entre dos vértices cualesquiera; de manera equivalente, es un DAG en el que, por cada vértice v , el subgrafo accesible desde v forma un árbol.
Problemas computacionales
Clasificación y reconocimiento topológico
La ordenación topológica es el problema algorítmico de encontrar una ordenación topológica de un DAG dado. Se puede resolver en tiempo lineal . El algoritmo de Kahn para la ordenación topológica construye la ordenación de 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 los vértices sin aristas entrantes en absoluto. Luego, agrega repetidamente un vértice de esta lista al final del orden topológico construido parcialmente y verifica si sus vecinos deben agregarse a la lista. El algoritmo termina cuando todos los vértices se han procesado de esta manera. Alternativamente, se puede construir un ordenamiento topológico invirtiendo una numeración posterior a un recorrido de gráfico de búsqueda en profundidad .
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 o, alternativamente, para algunos algoritmos de clasificación topológica, verificando que el algoritmo ordena correctamente todos los vértices sin cumplir una condición de error.
Construcción a partir de gráficos cíclicos
Cualquier grafo no dirigido puede convertirse en un DAG eligiendo un orden total para sus vértices y dirigiendo cada borde desde el punto final anterior en el orden al 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.
Cualquier gráfico 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 este tipo es NP-difícil de encontrar. Un gráfico dirigido arbitrario también se puede transformar en un DAG, llamado su condensación , al contraer cada uno de sus componentes fuertemente conectados en un solo supervertex. Cuando el gráfico ya es acíclico, sus conjuntos de vértices de retroalimentación y los conjuntos de arcos de retroalimentación más pequeños están vacíos , y su condensación es el gráfico en sí.
Cierre transitivo y reducción transitiva
El cierre transitivo de un DAG dado, con n vértices y m aristas, se puede construir en el tiempo O ( mn ) mediante el uso de búsqueda primero en amplitud o búsqueda en profundidad primero para probar la accesibilidad desde cada vértice. Alternativamente, se puede resolver en el tiempo O ( n ω ) donde ω <2.373 es el exponente para los algoritmos de multiplicación de matrices ; esta es una mejora teórica sobre el límite de O ( mn ) para gráficos densos .
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 estar conectados por un camino de longitud uno. La reducción transitiva consiste en los bordes que forman trayectorias de longitud uno que son las únicas trayectorias que conectan sus extremos. Por lo tanto, la reducción transitiva se puede construir en los mismos límites de tiempo asintóticos que el cierre transitivo.
Problema de cierre
El problema de cierre toma como entrada un gráfico acíclico vértice ponderado dirigido y busca el peso mínimo (o máximo) de un cierre - un conjunto de vértices C , de manera que no hay bordes dejan 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 de condensación del grafo. Puede resolverse en tiempo polinomial utilizando una reducción al problema de flujo máximo .
Algoritmos de ruta
Algunos algoritmos se vuelven más simples cuando se usan en DAG en lugar de gráficos generales, según el principio de ordenamiento topológico. Por ejemplo, es posible encontrar las rutas más cortas y más largas desde un vértice inicial dado 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 para que sea la longitud mínima o máxima obtenida a través de cualquier de sus bordes entrantes. Por el contrario, para gráficos arbitrarios, la ruta más corta puede requerir algoritmos más lentos, como el algoritmo de Dijkstra o el algoritmo de Bellman-Ford , y las rutas más largas en gráficos arbitrarios son NP-difíciles de encontrar.
Aplicaciones
Planificación
Las representaciones de gráficos acíclicos dirigidos de ordenamientos parciales tienen muchas aplicaciones en la programación de sistemas de tareas con restricciones de ordenamiento. Una clase importante de problemas de este tipo se refieren a colecciones de objetos que necesitan ser actualizados, tales como las células de una hoja de cálculo después de una de las células se ha cambiado, o los archivos objeto de una pieza de software después de su código fuente ha sido cambió. En este contexto, un gráfico de dependencia es un gráfico que tiene un vértice para cada objeto a actualizar y un borde que conecta dos objetos cuando uno de ellos necesita actualizarse antes que el otro. En este gráfico, un ciclo se denomina dependencia circular y, por lo general, no se permite, 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.
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 usa debe recalcularse antes que la expresión que lo usa. Ordenar topológicamente el gráfico de dependencia, y usar este orden topológico para programar las actualizaciones de la celda, permite que toda la hoja de cálculo se actualice con una sola evaluación por celda. Problemas similares de ordenación de tareas surgen en archivos MAKE para la compilación de programas y la programación de instrucciones para la optimización de programas de computadora de bajo nivel.
La técnica de evaluación y revisión de programas (PERT) utiliza una formulación algo diferente basada en DAG de las restricciones de programación , un método para la gestión de grandes proyectos humanos que fue una de las primeras aplicaciones de los 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. Los hitos individuales se pueden programar de acuerdo con las longitudes de los caminos más largos que terminan en sus vértices.
Redes de procesamiento de datos
Puede usarse 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 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. Los esquemas de circuitos electrónicos 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 en flujos de datos y las conexiones entre las salidas de algunas operaciones y las entradas de otras. Estos lenguajes pueden resultar convenientes para describir tareas repetitivas de procesamiento de datos, en las que se aplica la misma colección de operaciones conectadas acíclicamente 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.
En los compiladores , el código de línea recta (es decir, secuencias de declaraciones sin bucles o 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. 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 gran sistema de software deben formar un gráfico acíclico dirigido.
Las redes neuronales feedforward son otro ejemplo.
Estructuras causales
Los gráficos en los que los vértices representan eventos que ocurren en un tiempo definido, y donde los bordes siempre apuntan desde el vértice de tiempo temprano a un vértice de tiempo tardío del borde, 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 sigue cualquier camino en el gráfico, por lo que nunca puede volver 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 del conjunto causal de la gravedad cuántica, aunque en este caso los gráficos considerados son transitivamente completos . En el ejemplo del historial de versiones, cada versión del software está asociada a una hora única, normalmente la hora en que se guardó, confirmó o publicó la versión. Para los gráficos de citas, 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 momento 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 gráfico acíclico dirigido. 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. En este contexto, el gráfico moral de un DAG es el gráfico no dirigido creado al agregar 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. 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. En epidemiología , por ejemplo, estos diagramas se utilizan a menudo para estimar el valor esperado de diferentes opciones de intervención.
Lo contrario también es cierto. Es decir, en cualquier aplicación representada por un gráfico acíclico dirigido, existe una estructura causal, ya sea un orden explícito o tiempo en el ejemplo o un orden que puede derivarse de la estructura del gráfico. Esto se debe a que todos los gráficos acíclicos dirigidos tienen un orden topológico , es decir, hay al menos una forma de poner los vértices en un orden tal que todos los bordes apunten en la misma dirección a lo largo de ese orden.
Genealogía e historial de versiones
Los árboles genealógicos pueden verse como gráficos acíclicos dirigidos, con un vértice para cada miembro de la familia y un borde para cada relación entre padres e hijos. A pesar del nombre, estos gráficos no son necesariamente árboles debido a la posibilidad de matrimonios entre parientes (por lo que un niño tiene un ancestro común tanto del lado de la madre como del padre) que provocan el colapso del pedigrí . Los gráficos de descendencia matrilineal (relaciones "madre" entre mujeres) y descendencia patrilineal (relaciones "paternales" entre hombres) son árboles dentro de este gráfico. Como nadie puede convertirse en su propio antepasado, los árboles genealógicos son acíclicos.
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.
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 bordes de cada triángulo a los otros dos o tres triángulos que lo reemplazan. Esta estructura permite que las consultas de ubicación de puntos sean respondidas 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 historial DAG, en cada paso moviéndose 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 .
Gráficos de citas
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 "Redes de artículos científicos" de Derek J. de Solla Price, quien llegó a producir el primer modelo de una red de citas, el modelo de Price . 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 de los tribunales proporcionan otro ejemplo, ya que los jueces apoyan sus conclusiones en un caso recordando otras decisiones anteriores tomadas en casos anteriores. Un último ejemplo lo proporcionan las patentes que deben hacer referencia al estado de la técnica anterior, patentes anteriores que son relevantes para la reivindicación de patente actual. Teniendo en cuenta las propiedades especiales de los gráficos acíclicos dirigidos, se pueden analizar redes de citas con técnicas no disponibles al analizar los gráficos generales considerados en muchos estudios que utilizan análisis de redes . Por ejemplo, la reducción transitiva brinda una nueva perspectiva de las distribuciones de citas que se encuentran en diferentes aplicaciones, destacando diferencias claras en los mecanismos que crean redes de citas en diferentes contextos. 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 dado .
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 estos se pueden encontrar mediante el uso de resultados derivados de la versión no dirigida del modelo de Price , el modelo 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 n-ésimo nodo agregado a la red hasta el primer nodo de la red, se escala como .
Compresión de datos
Los gráficos acíclicos dirigidos también se pueden usar 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 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 sola fuente y con bordes etiquetados con 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. 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 cuerdas se llama trie . Un gráfico de palabras acíclico dirigido ahorra espacio en un trie al permitir que las rutas diverjan y se vuelvan a unir, de modo que un conjunto de palabras con los mismos sufijos posibles se pueda representar mediante un único vértice de árbol.
La misma idea de usar un DAG para representar una familia de caminos ocurre en el diagrama de decisión binario , una estructura de datos basada en DAG para representar funciones binarias. En un diagrama de decisión binario, cada vértice no sumidero está etiquetado con el nombre de una variable binaria, y cada sumidero y cada borde está etiquetado 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 que se encuentra siguiendo una ruta, comenzando desde el vértice de fuente única, 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 los caminos se reincorporen cuando coinciden en los resultados de todas las decisiones restantes.
Referencias
enlaces externos
- Weisstein, Eric W. , "Acyclic Digraph" , MathWorld
- DAGitty : una herramienta en línea para crear DAG