Grafo dirigido acíclico

Un ejemplo de un grafo dirigido acíclico

En matemáticas y Ciencias de la computación, un Grafo dirigido acíclico (DAG ⁱ/ˈdæɡ/), es un Grafo dirigido con no ciclos dirigidos. Es decir, está formado por una colección de vértices y bordes dirigidos, cada borde conectando un vértice a otro, tal que no hay ninguna manera de empezar en un vértice v y seguir una secuencia de aristas que eventualmente bucles hacia v otra vez.

DAGs pueden utilizarse para modelar muchos tipos diferentes de información. El accesibilidad relación en forma de un DAG un orden parcialy cualquier finito orden parcial puede ser representado por un DAG usando accesibilidad. Una colección de las tareas que deben ordenarse en una secuencia, sujeto a las limitaciones que deben realizarse antes que otros, ciertas tareas puede representarse como un DAG con un vértice para cada tarea y un borde para cada restricción; algoritmos para Ordenación topológica pueden ser utilizados para generar una secuencia válida. Además, DAGs pueden utilizarse como una representación de una colección de secuencias con superposición subsecuencias de uso eficiente del espacio. DAGs también se utilizan para representar los sistemas de eventos o potenciales y el relaciones causales entre ellos. DAGs también pueden ser utilizados para modelar los procesos en que los flujos de datos en una dirección coherente a través de una red de procesadores.

El concepto correspondiente para gráficos sin señas es un bosque, un gráfico sin señas sin ciclos. Elegir una orientación para un bosque produce un especial tipo de Grafo acíclico llamado dirigido a polytree. Sin embargo, hay muchas otras clases de grafo dirigido acíclico que no están formados por orientar las aristas de un Grafo acíclico sin señas, y cada gráfico sin señas tiene una orientación acíclico, una asignación de una dirección para sus bordes que lo convierte en un grafo dirigido acíclico. Por esta razón puede ser más precisa llamar dirigido acíclico acíclico dirigido o dígrafos acíclicos.

Propiedades matemáticas

Accesibilidad, cierre transitivo y reducción transitiva

A Diagrama de Hasse representando el ⊆ orden parcial entre los subconjuntos de un conjunto de tres elementos.

Cada uno dirigido gráfico acíclico da lugar a un orden parcial ≤ en sus vértices, donde u ≤ v exactamente cuando existe un camino dirigido desde u Para v en el DAG. Sin embargo, muchos diferentes que dags pueden dar lugar a esto mismo accesibilidad relación: por ejemplo, el DAG con dos bordes a → b y b → c tiene la misma accesibilidad como el gráfico con tres cantos a → b, b → c, y a → c. If G es un DAG, su reducción transitiva es el gráfico con los bordes del menor número que representa la misma accesibilidad como Gy su cierre transitivo es el gráfico con la mayoría de los bordes que representa la misma accesibilidad. La reducción transitiva y cierre transitivo son únicamente dos definidos para DAGs; en cambio, para un grafo dirigido no es acíclico, puede haber más de un subgráfico mínimo con la misma relación de accesibilidad.

El cierre transitivo de G tiene un borde u → v para cada pareja relacionado u≤v de los distintos elementos en la relación de accesibilidad de Gy por lo tanto puede ser considerado como una traducción directa de la accesibilidad relación ≤ en términos de teoría de gráfico: cada conjunto parcialmente ordenado puede traducirse en un DAG de esta manera. If a DAG G representa un orden parcial ≤, entonces la reducción transitiva de G es un subgráfico de G con un borde u → v para cada pareja en el relación de cobertura de ≤; transitivas reducciones son útiles para visualizar las órdenes parciales que representan, porque tienen bordes menos que otros gráficos que representan las mismas órdenes y por lo tanto conducen a simple dibujos de gráfico. A Diagrama de Hasse de un orden parcial es un dibujo de la reducción transitiva en el cual se muestra la orientación de cada borde colocando el vértice a partir del borde en una posición más baja que su vértice final.

Ordenación topológica

Cada Grafo acíclico dirigido tiene un Ordenación topológica, un ordenamiento de los vértices tal que el extremo de salida de cada borde se produce antes en el orden que el extremo final del borde. En general, este orden no es la única; un DAG tiene una única Ordenación topológica si y sólo si tiene un camino dirigido que contiene todos los vértices, en cuyo caso el ordenamiento es el mismo que el orden en que aparecen los vértices en el camino. La familia de ordenamientos topológicas de un DAG es igual a la familia de extensiones de lineales de la relación de accesibilidad para el DAG, Así que cualquier dos gráficos que representan el mismo orden parcial tienen el mismo conjunto de órdenes topológicos.

Enumeración combinatoria

El enumeración de gráfico problema de conteo dirigido acíclico fue estudiado por Robinson (1973). El número de DAGs en n Etiquetado nodos, para n= 0, 1, 2, 3,..., (permitiendo que estos números que aparezcan en cualquier orden en una ordenación topológica del DAG) es

1, 1, 3, 25, 543, 29281, 3781503... (secuencia A003024 en OEIS).

Estos números pueden ser computados por la relación de recurrencia

$a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.$

Eric W. Weisstein conjeturó, y McKay et al (2004) demostró, que el mismo números de cuenta de la matrices (0,1) en el que todos valores propios son positivos números reales. La prueba es biyectiva:: una matriz A es un matriz de adyacencia de un DAG si y sólo si A+I es una matriz (0,1) con valores propios todos positivos, donde I denota la matriz identidad. Porque no puedes tener un DAG Self-lazos, su matriz de adyacencia debe tener una cero diagonal, añadiendo así I conserva la propiedad de que todos los coeficientes de la matriz son 0 ó 1.

Familias relacionadas de gráficos

A polytree es un grafo dirigido formado por orientar las aristas de un árbol gratis. Cada polytree es un DAG. En particular, esto es cierto en el arborescences formado por dirigir todos los bordes hacia fuera de la raíz de un árbol. A multitree (también llamado un gráfico fuertemente sin ambigüedades o manglares) es un grafo dirigido en el cual en la mayoría hay un camino dirigido (en cualquier dirección) entre cualquier dos nodos; equivalente, es un DAG en el cual, para cada nodo v, el conjunto de nodos accesibles desde v formas de un árbol.

Problemas computacionales

Ordenación topológica y reconocimiento

Artículo principal: Ordenación topológica

Ordenación topológica es el problema algorítmico de encontrar ordenamientos topológicas; se puede resolver en tiempo lineal. Algoritmo de Kahn para Ordenación topológica construye el vértice ordenar directamente, mantener una lista de vértices que no tienen bordes se conectan a los vértices que ya no se han enumerado y repetidamente añadiendo un tal vértice hasta el final de la lista que se está construyendo. Alternativamente, una ordenación topológica puede construirse mediante la inversión de un postorder numeración de una búsqueda en profundidad gráfico traversal.

También es posible comprobar si un determinado grafo dirigido es un DAG en tiempo lineal, ya sea por intentar encontrar una ordenación topológica y entonces la prueba para cada borde si es válido el pedido resultante o alternativamente, para algunos topológica clasificación algoritmos, verificando el algoritmo con éxito todos los vértices sin cumplir una condición de error.

Construcción de gráficos cíclicos

Cualquier gráfico sin señas puede ser hecho en un DAG eligiendo un total de la orden para sus vértices y orientar cada borde desde el extremo anterior en el orden al extremo posterior. Sin embargo, diversas órdenes totales pueden conducir a la misma orientación acíclico. El número de orientaciones acíclicos es igual a |χ (−1) |, donde χ es la Polinomio cromático del gráfico determinado.

Cualquier dirigido gráfico puede ser hecho en un DAG quitando un sistema de retroalimentación vértice o un retroalimentación Arco conjunto. Sin embargo, el más pequeño es tan NP-hard Buscar. Un grafo dirigido arbitrario puede transformarse también en un DAG, llamado su condensación, mediante la contratación de cada uno de sus componentes fuertemente conectados en una sola supervertex. Cuando el gráfico acíclico, su menor retroalimentación vértice conjuntos y retroalimentación arco son vacío, y su condensación es el gráfico de sí mismo.

Cierre transitivo y reducción transitiva

El cierre transitivo de un determinado DAG, con n vértices y m bordes, puede construirse en el tiempo O(mn) utilizando cualquiera búsqueda en amplitud o búsqueda en profundidad para probar la accesibilidad de cada vértice. Alternativamente, se puede resolver en tiempo O(n^ω) donde ω< 2.373 es el exponente de algoritmos de multiplicación rápida de la matriz; Esto es una mejora teórica sobre la O(mn) con destino a gráficos de densos.

En todos estos algoritmos cierre transitivo, es posible distinguir pares de vértices que son accesibles por al menos una ruta de dos o más de los pares que sólo pueden ser conectados por un camino de longitud-uno de longitud. La reducción transitiva consiste en los bordes que forman caminos de longitud-uno que son las únicas vías conectando sus extremos. Por lo tanto, la reducción transitiva puede construirse en los límites de tiempo asintótico misma como el cierre transitivo.

Problema de cierre

Artículo principal: Problema de cierre

El problema de cierre toma como entrada un Grafo acíclico dirigido con pesas en sus vértices y busca el peso mínimo (o máximo) de un encierro, un conjunto de vértices sin bordes salientes. (El problema puede formular para gráficos dirigidos sin la asunción de acyclicity, pero con ninguna generalidad mayor, porque en este caso es equivalente al mismo problema de la condensación del gráfico). Se puede resolver en tiempo polinomial usando una reducción a la problema de flujo máximo.

Aplicaciones

Algoritmos de camino

Algunos algoritmos se convierten en más sencillos cuando se utiliza en DAGs en lugar de gráficos generales, basados en el principio de Ordenación topológica. Por ejemplo, es posible encontrar caminos más cortos y rutas más largas desde un vértice inicial dado en DAGs en tiempo lineal procesando los vértices en un orden topológico, y calcular la longitud del camino de cada vértice a la longitud mínima o máxima obtenida a través de cualquiera de sus bordes entrantes. En contraste, para gráficos arbitrarios la ruta más corta requieran algoritmos más lentos como Algoritmo de Dijkstra o el Algoritmo de Bellman-Ford, y son más largos caminos en grafos arbitrarios NP-hard Buscar.

Programación

DAG representaciones de ordenamientos parciales tienen muchas aplicaciones problemas de programación para los sistemas de tareas con ordenar restricciones. Por ejemplo, puede utilizarse un DAG para describir las dependencias entre las células de un hoja de cálculo:: Si una célula se calcula mediante una fórmula que implica el valor de una segunda célula, dibujar un borde de DAG desde la segunda célula al primero. Si cambian los valores de entrada a la hoja de cálculo, todos los valores restantes de la hoja de cálculo pueden recalculó con una sola evaluación por la célula, por ordenar las células topológico y reevaluación de cada celda en este orden. Surgen problemas similares de tarea ordenar en Makefiles para la compilación del programa, instrucciones de programación para la optimización del programa informático bajo nivel, y Programación PERT para la gestión de grandes proyectos humanos. Gráficos de dependencia sin dependencias circulares formulario había dirigido acíclico.

Redes de procesamiento de datos

Un grafo dirigido puede utilizarse para representar una red de procesamiento de elementos; en esta formulación, datos entra en un elemento de procesamiento a través de sus bordes entrantes y deja el elemento a través de sus bordes salientes. Ejemplos de esto incluyen lo siguiente:

• En el diseño de circuitos electrónicos, un Lógica combinatoria circuito es un sistema acíclico de puertas lógicas calcula una función de una entrada, donde la entrada y salida de la función están representados como individuales brocas.
• Flujo de datos lenguajes de programación describen los sistemas de valores que están relacionados entre sí por un Grafo acíclico dirigido. Cuando cambia un valor, sus sucesores se recalculan; cada valor se evaluará en función de sus predecesores en el DAG.
• En compiladores, código de línea recta (es decir, secuencias de declaraciones sin bucles o ramas condicionales) puede ser representado por un DAG describiendo las entradas y salidas de cada una de las operaciones aritméticas realizadas dentro del código; Esta representación permite el compilador realizar eliminación de subexpresiones comunes eficientemente.
• En la mayoría hoja de cálculo sistemas, la gráfico de dependencia conecta a una célula a otra si las primeras tiendas de celda una fórmula que utiliza el valor de la segunda célula deben ser un Grafo acíclico dirigido. Ciclos de dependencias se prohibió porque causan las células implicadas en el ciclo para que no tenga un valor bien definido. Adicionalmente, que requieran las dependencias para ser acíclicos, permite una tipo topológico para ser utilizado para programar los nuevos cálculos de los valores de celda cuando se cambia la hoja de cálculo.

Estructuras causales

Gráficos que tienen los vértices que representa los eventos y los bordes que representa relaciones causales entre los eventos, a menudo son acíclicos – organizar los vértices en orden lineal del tiempo, todas las flechas apuntan en la misma dirección que el tiempo, de padre a hijo (debido a la causalidad que afectan el futuro, no en el pasado) y tienen pues no hay bucles.

Por ejemplo, un Red bayesiana representa un sistema de eventos probabilísticos como nodos de un grafo dirigido acíclico, en el cual puede calcularse la probabilidad de un evento de las probabilidades de sus predecesores en el DAG. En este contexto, la gráfico de moral de un DAG es el gráfico sin señas creado mediante la adición de un borde (no dirigido) entre todos los padres del mismo nodo (llamado a veces casar) y luego reemplazar los bordes está dirigidos por los bordes sin señas.

Otro tipo de gráfico con una estructura causal similar es un Diagrama de influencia, los nodos que representan o decisiones hecha o desconoce la información, y los bordes de los cuales representan influencias causales de un nodo a otro. En Epidemiología, por ejemplo, estos diagramas son utilizados a menudo para estimar el valor esperado de diferentes opciones de intervención. El papel de DAGs en estas aplicaciones es convertir hipótesis causales en restricciones independencias condicionales, que pueden ser leídas desde el DAG usando de la perla d-separación y probado en los datos.

Historia de la genealogía y versión

Árboles genealógicos también puede ser visto como dirigido acíclico, con un vértice por cada miembro de la familia y una ventaja para cada relación padre-hijo. A pesar del nombre, estos gráficos no son necesariamente los árboles debido a la posibilidad de matrimonios entre parientes lejanos (para que un niño tiene un antepasado común a lado de la madre y el padre) causando colapso de pedigrí. (Las gráficas de matrilineal descenso (relaciones de "madre" entre las mujeres) y paterna descenso (relaciones de "padre" entre los hombres) son árboles dentro de este gráfico). Porque nadie puede convertirse en su propio antepasado, estos gráficos son acíclicos.

Por la misma razón, el historial de versiones sobre un control de revisión distribuida sistema generalmente tiene la estructura de un grafo dirigido acíclico, en el cual hay un vértice para cada revisión y un borde conectando pares de revisiones que se derivan directamente de unos a otros; Estos no son los árboles en general debido a las fusiones.

En muchos al azar algoritmos en geometría computacional, el algoritmo mantiene un historia DAG representando la historia de la versión de una estructura geométrica en el transcurso de una secuencia de cambios en la estructura. Por ejemplo en un aleatorio incremental algoritmo para el Triangulación de Delaunay, los cambios de triangulación, mediante la sustitución de un triángulo por tres triángulos más pequeños cuando se agrega cada punto y por operaciones de "volteo" que reemplazar pares de triángulos por otro par de triángulos. La historia DAG para este algoritmo tiene un vértice de cada triángulo construido como parte del algoritmo y los bordes de cada triángulo con dos o tres otros triángulos que reemplazarlo. Permite trazar un camino a través de este DAG que representa la secuencia de triángulos que contienen un punto individual Ubicación del punto consultas deben responder eficazmente.

Compresión de datos

Otro tipo de aplicación de dirigido acíclico se presenta en la representación concisa de un conjunto de secuencias como caminos en un gráfico. Por ejemplo, la Grafo dirigido acíclico palabra es un estructura de datos en informática, formado por un Grafo acíclico dirigido con una sola fuente y con bordes marcados por letras o símbolos; los caminos de la fuente de las pilas en este gráfico representan un conjunto de cuerdas, tales como palabras en inglés. Cualquier conjunto de secuencias puede ser representado como caminos en un árbol, formando un nodo de árbol para cada prefijo de una secuencia y haciendo que el padre de uno de estos nodos representan la secuencia con un elemento menos; el árbol formado de esta manera para un conjunto de cadenas se llama un trie. Un grafo dirigido acíclico palabra ahorra espacio sobre un trie permitiendo caminos divergen y volver a unir, para que un conjunto de palabras con los mismos posibles sufijos puede ser representado por un nodo de árbol.

La misma idea de usar un DAG para representar una familia de caminos se produce en el Diagrama de decisión binaria, una estructura de datos basada en DAG para representar las funciones binarias. En un diagrama de decisión binaria, cada vértice del fregadero no está etiquetado con el nombre de una variable binaria, y cada fregadero y cada borde es marcado por 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 fregadero se encuentra siguiendo un camino, a partir de la cima de la fuente, que en cada vértice del disipador no sigue el borde saliente etiquetado con el valor de la variable de ese vértice. Sólo como se indica en los gráficos acíclicos palabra pueden considerarse como una forma comprimida de intentos, los diagramas de decisión binaria pueden considerarse como formas comprimidas de árboles de decisión Ahorre espacio permitiendo caminos volver cuando están de acuerdo con los resultados de todas las decisiones restantes.

Enlaces externos

• Weisstein, Eric W., "Acíclico dígrafo", MathWorld.

Otras Páginas

• KXLA
• LeeMon
• Embolizacion
• Amirabad-e Sorkh Mahalleh
• Samsung Galaxy Young
• Comparacion de soluciones de autenticacion
• Compensacion del trabajador (Alemania)
• Todd Rogers
• Parametros de dispersion