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 finito gráfico dirigido con no hay ciclos dirigidos . Es decir, consiste en finitos vértices y aristas (también llamados arcos ), con cada arista dirigida de un vértice a otro, de modo que no hay forma de comenzar en ningún vértice vy siga una secuencia de bordes constantemente dirigida que eventualmente regresa a v nuevamente. De manera equivalente, un DAG es un gráfico dirigido que tiene un orden topológico , una secuencia de los vértices de tal manera que cada borde se dirige de principio a fin en la secuencia.
) es un finito gráfico dirigido con no hay ciclos dirigidos . Es decir, consiste en finitos vértices y aristas (también llamados arcos ), con cada arista dirigida de un vértice a otro, de modo que no hay forma de comenzar en ningún vértice vy siga una secuencia de bordes constantemente dirigida que eventualmente regresa a v nuevamente. De manera equivalente, un DAG es un gráfico dirigido que tiene un orden topológico , una secuencia de los vértices de tal manera que cada borde se dirige de principio a fin en la secuencia.
Los DAG pueden modelar muchos tipos diferentes de información. Por ejemplo, una hoja de cálculo se puede modelar como un DAG, con un vértice para cada celda y un borde siempre que la fórmula en una celda use el valor de otra; Se puede usar un orden topológico de este DAG para actualizar todos los valores de celda cuando se cambia la hoja de cálculo. Del mismo modo, los ordenamientos topológicos de los DAG se pueden utilizar para ordenar las operaciones de compilación en un archivo MAKE . La técnica de evaluación y revisión del programa (PERT) utiliza DAG para modelar los hitos y actividades de grandes proyectos humanos, y programar estos proyectos para usar el menor tiempo total posible. Bloques lógicos combinacionales en el diseño de circuitos electrónicos y las operaciones en la programación del flujo de datos.idiomas, implican redes acíclicas de elementos de procesamiento. Los DAG también pueden representar colecciones de eventos y su influencia entre sí, ya sea en una estructura probabilística como una red bayesiana o como un registro de datos históricos como árboles genealógicos o las historias de versiones de sistemas de control de revisión distribuidos . Los DAG también se pueden usar como una representación compacta de datos de secuencia, como la representación gráfica de palabras acíclicas dirigidas de una colección de cadenas, o la representación del diagrama de decisión binario de secuencias de elecciones binarias. Más abstractamente, la relación de accesibilidad en un DAG forma un orden parcial, y cualquier orden parcial finito puede ser representado por un DAG usando accesibilidad.
Los problemas computacionales importantes del tiempo polinómico en los DAG incluyen la clasificación topológica (cálculo de un orden topológico), la construcción del cierre transitivo y la reducción transitiva (los DAG más grandes y más pequeños con la misma relación de accesibilidad, respectivamente) de conjuntos, y el problema de cierre , en el que el El objetivo es encontrar un subconjunto de vértices de peso mínimo sin bordes que los conecten con el resto del gráfico. Transformar un gráfico dirigido con ciclos en un DAG eliminando la menor cantidad posible de vértices o bordes (el problema del conjunto de vértices de retroalimentación y el conjunto de bordes de retroalimentación , respectivamente) es un NP-hardproblema, pero cualquier gráfico dirigido puede convertirse en un DAG (su condensación ) al contraer cada componente fuertemente conectado en un solo supervertex. Los problemas de encontrar rutas más cortas y más largas se pueden resolver en DAG en tiempo lineal , en contraste con los gráficos arbitrarios para los que los algoritmos de ruta más corta son más lentos y los problemas de ruta más largos son NP-hard.
El concepto correspondiente para gráficos no dirigidos es un bosque , un gráfico no dirigido sin ciclos. Elegir una orientación para un bosque produce un tipo especial de gráfico acíclico dirigido llamado polytree . Sin embargo, hay muchos otros tipos de gráficos acíclicos dirigidos que no se forman orientando los bordes de un gráfico acíclico no dirigido. Además, cada gráfico no dirigido tiene una orientación acíclica , una asignación de una dirección para sus bordes que lo convierte en un gráfico acíclico dirigido. Para enfatizar que los DAG no son lo mismo que las versiones dirigidas de gráficos acíclicos no dirigidos, algunos autores los llaman gráficos dirigidos acíclicos [1] o dígrafos acíclicos .
Definiciones [ editar ]
Un gráfico está formado por una colección de vértices y aristas , donde los vértices son objetos sin estructura que están conectados 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. Una ruta en un gráfico dirigido puede describirse mediante una secuencia de bordes que tiene la propiedad de que el vértice final de cada borde de la secuencia es el mismo que el vértice inicial del siguiente borde de la secuencia; una ruta 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 gráfico dirigido es accesible desde otro vértice u cuando existe una ruta que comienza en u y termina en v . Como caso especial, cada vértice se considera accesible desde sí mismo (por una ruta con bordes cero). 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 alcanzarse a sí mismo a través de un camino no trivial [4]
Una ordenación topológica de un gráfico dirigido es una ordenación de sus vértices en una secuencia, de modo que para cada borde el vértice inicial del borde se produce antes en la secuencia que el vértice final del borde. Un gráfico que tiene un orden topológico no puede tener ningún ciclo, porque el borde en el vértice más temprano de un ciclo tendría que estar orientado de manera incorrecta. Por lo tanto, cada gráfico con un orden topológico es acíclico. Por el contrario, cada gráfico acíclico dirigido tiene al menos un orden topológico. Por lo tanto, esta propiedad se puede usar como una definición alternativa de los gráficos acíclicos dirigidos: son exactamente los gráficos que tienen ordenamientos topológicos. [2]
Propiedades matemáticas [ editar ]
Accesibilidad, cierre transitivo y reducción transitiva [ editar ]
La relación de accesibilidad en cualquier gráfico acíclico dirigido puede formalizarse 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 una ruta dirigida de u a v en el DAG; es decir, cuando v es accesible desde u . [5] Sin embargo, diferentes DAG pueden dar lugar a la misma relación de accesibilidad y el mismo orden parcial. [6] Por ejemplo, el DAG con dos bordes un → b y b→ c tiene la misma relación de accesibilidad que la gráfica con tres aristas a → b , b → c , y a → 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 una ventaja U → V cada vez que u puede llegar v . Es decir, tiene una ventaja para cada par relacionado u ≤ v de elementos distintos en la relación de accesibilidad de G y, por lo tanto, puede considerarse como una traducción directa de la relación de accesibilidad ≤ 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 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 se puede representar 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 una subgrafía de G , formada descartando los bordes u → v para los cuales G también contiene una ruta más larga que conecta los mismos dos vértices. Al igual que el cierre transitivo, la reducción transitiva se define de manera única para los DAG. En contraste, 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]
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 pedidos parciales que representan, porque tienen menos aristas que otros gráficos que representan los mismos pedidos y, por lo tanto, conducen a dibujos de gráficos más simples . Un diagrama de Hassede un orden parcial es un dibujo de la reducción transitiva en la que se muestra la orientación de cada borde colocando el vértice inicial del borde en una posición más baja que su vértice final. [8]
Ordenamiento topológico [ editar ]
Cada gráfico acíclico dirigido tiene un orden topológico , un orden de los vértices de tal manera que el punto final inicial de cada borde ocurre antes en el orden que el punto final final del borde. La existencia de tal ordenamiento puede usarse para caracterizar DAG: un gráfico dirigido es un DAG si y solo si tiene un ordenamiento topológico. 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 accesibilidad para el DAG, [10] por lo que dos gráficos que representan el mismo orden parcial tienen el mismo conjunto de órdenes topológicos.
Enumeración combinatoria [ editar ]
El gráfico enumeración problema de contar gráficos acíclicos dirigidos fue estudiada 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 que aparecen estos números en un orden topológico del DAG)
Estos números pueden calcularse por 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 autovalores son números reales positivos . La prueba es biyectiva : una matriz A es una matriz de adyacencia de un DAG si y sólo si A + I es A (0,1) de la matriz con todos los valores propios positivos, donde I denota la matriz de 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 Iconserva la propiedad de que todos los coeficientes de la matriz son 0 o 1. [13]
Familias relacionadas de gráficos [ editar ]
Un polytree es un gráfico dirigido formado al orientar los bordes de un árbol libre . [14] Cada polytree es un DAG. En particular, esto es cierto para las arborescencias formadas al dirigir todos los bordes hacia afuera desde las raíces de un árbol.
Un multitree (también llamado gráfico muy inequívoco o manglar) es un gráfico dirigido en el que hay como máximo un camino dirigido (en cualquier dirección) entre dos vértices; equivalentemente, es un DAG en el cual, para cada vértice v , el subgrafo accesible desde v forma un árbol. [15]
Problemas computacionales [ editar ]
Clasificación y reconocimiento topológicos [ editar ]
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 clasificación topológica construye el ordenamiento de vértices directamente. Mantiene una lista de vértices que no tienen bordes entrantes de otros vértices que aún no se han incluido en el orden topológico parcialmente construido; inicialmente esta lista consiste en los vértices sin bordes 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 orden topológico invirtiendo una numeración de postorder de un recorrido de gráfico de búsqueda de profundidad primero . [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 clasificación topológica, al verificar que el algoritmo ordena con éxito todos los vértices sin cumplir una condición de error. [17]
Construcción a partir de gráficos cíclicos [ editar ]
Cualquier gráfico 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 hasta el punto final posterior. La orientación resultante de los bordes se denomina orientación acíclica . Diferentes órdenes totales pueden conducir a la misma orientación acíclica, por lo que un gráfico n- vértice 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 puede convertirse en un DAG eliminando un conjunto de vértices de retroalimentación o un conjunto de arco de retroalimentación , un conjunto de vértices o bordes (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 puede transformarse en un DAG, llamado condensación , al contraer cada uno de sus componentes fuertemente conectados en un solo supervertex. [21] Cuando el gráfico ya es acíclico, sus conjuntos de vértices de retroalimentación más pequeños y sus conjuntos de arco de retroalimentación están vacíos , y su condensación es el gráfico mismo.
Cierre transitivo y reducción transitiva [ editar ]
El cierre transitivo de un DAG dado, con n vértices ym aristas, puede construirse en el tiempo O ( mn ) mediante el uso de la búsqueda de amplitud o de búsqueda de profundidad para probar la accesibilidad desde cada vértice. [22] Alternativamente, se puede resolver en el tiempo O ( n ω ) donde ω <2 .373="" font=""> es el exponente de los algoritmos de multiplicación de matriz rápida ; Esta 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 llegar por al menos un camino de longitud dos o más de pares que solo se pueden conectar por un camino de longitud uno. La reducción transitiva consiste en los bordes que forman rutas de longitud uno que son las únicas rutas 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]
Problema de cierre [ editar ]
El problema del cierre toma como entrada un gráfico acíclico dirigido con pesos en sus vértices y busca el peso mínimo (o máximo) de un cierre, un conjunto de vértices sin bordes salientes. (El problema puede formularse para gráficos dirigidos sin el supuesto de aciclicidad, pero sin mayor generalidad, porque en este caso es equivalente al mismo problema en la condensación del gráfico). Puede resolverse en tiempo polinómico usando una reducción al problema de flujo máximo . [25]
Algoritmos de ruta [ editar ]
Algunos algoritmos se vuelven más simples cuando se usan en DAG en lugar de gráficos generales, según el principio del ordenamiento topológico. Por ejemplo, es posible encontrar 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 como la longitud mínima o máxima obtenida a través de cualquier de sus bordes entrantes. [26] En contraste, para los 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 los gráficos arbitrarios son NP-difíciles de encontrar. [28]
Aplicaciones [ editar ]
Programación [ editar ]
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. [29] Una clase importante de problemas de este tipo se refiere a colecciones de objetos que necesitan actualizarse, como las celdas de una hoja de cálculo después de que una de las celdas ha sido cambiada, o los archivos de objetos de un software después de su origen. 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 a actualizar, y un borde que conecta dos objetos cada vez que uno de ellos necesita actualizarse antes que el otro. Un ciclo en este gráfico se llama 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 cambiada. Para este problema, las tareas que se programarán son los nuevos cálculos de los valores de las 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. Al ordenar topológicamente el gráfico de dependencia, y al usar este orden topológico para programar las actualizaciones de la celda, se puede actualizar toda la hoja de cálculo con una sola evaluación por celda. [31] Problemas similares de ordenamiento de tareas surgen en archivos MAKE para compilación de programas [31]y 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 del programa (PERT) utiliza una formulación de restricciones de programación basada en DAG algo diferente , un método para la gestión de grandes proyectos humanos que fue una de las primeras aplicaciones de 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, conectando 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íticadel 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]
Redes de procesamiento de datos [ editar ]
Se puede usar 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 compuertas lógicas que calcula la 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 puede usarse como entrada a menos que sea capturada por un elemento de registro o estado que mantenga sus propiedades acíclicas. [34] 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 ser convenientes para describir tareas repetitivas de procesamiento de datos, en las cuales 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. [35]
En los compiladores , el código de línea recta (es decir, secuencias de sentencias sin bucles o ramificaciones condicionales) puede estar representado por 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 que el compilador realice 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 gran sistema de software deben formar un gráfico acíclico dirigido. [37]
Estructuras causales [ editar ]
Los gráficos en los que los vértices representan eventos que ocurren en un momento definido, y donde los bordes siempre apuntan desde el vértice temprano hasta un vértice 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 ruta en el gráfico, por lo que nunca puede volver a un vértice en una ruta. 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 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, generalmente la hora en que se guardó, confirmó o lanzó la versión. Para los gráficos de citas, los documentos se publican al mismo tiempo y solo pueden referirse 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 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 al agregar 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 los bordes representan influencias causales de un vértice a otro. [41] En epidemiología , por ejemplo, estos diagramas a menudo se usan para estimar el valor esperado de las 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, 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 colocar 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 [ editar ]
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 padre-hijo. [44] 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 antepasado común tanto del lado de la madre como del padre) que causa el colapso de pedigrí . [45] Las gráficas de descendencia matrilineal (relaciones "madre" entre mujeres) y descendencia patrilineal (relaciones "padre" entre hombres) son árboles dentro de esta gráfica. Como nadie puede convertirse en su propio antepasado, los árboles genealógicos son acíclicos. [46]
Por la misma razón, el historial de versiones de un sistema de control de revisión distribuido 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 el uno del otro. Estos no son árboles en general debido a las fusiones. [47]
En muchos algoritmos aleatorios en geometría computacional , el algoritmo mantiene un historial DAG 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 al reemplazar un triángulo por tres triángulos más pequeños cuando se agrega cada punto, y por operaciones de "volteo" que reemplazan pares de triángulos por un par diferente de triángulos. El DAG de historia para este algoritmo tiene un vértice para cada triángulo construido como parte del algoritmo, y los bordes de cada triángulo a los otros dos o tres triángulos que lo reemplazan. Esta estructura permiteconsultas de ubicación de puntos para ser 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 DAG del historial, en cada paso moviéndose al triángulo de reemplazo que contiene q . El triángulo final alcanzado en este camino debe ser el triángulo de Delaunay que contiene q . [48]
Gráficos de citas [ editar ]
En un gráfico de citas, los vértices son documentos con una sola 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 trabajos académicos como se señala en el artículo de 1965 "Redes de documentos científicos" [49] por Derek J. de Solla Price . En este caso, el recuento de citas de un documento es solo el grado del vértice correspondiente de la red de citas. Esta es una medida importante en el análisis de citas . Sentencias judicialesbrinde otro ejemplo ya que los jueces respaldan sus conclusiones en un caso al recordar otras decisiones anteriores tomadas en casos anteriores. Un último ejemplo lo proporcionan las patentes que deben referirse a la técnica anterior anterior , patentes anteriores que son relevantes para la solicitud de patente actual. Al tomar en cuenta las propiedades especiales de los gráficos acíclicos dirigidos, uno puede analizar estos gráficos con técnicas que no están disponibles al analizar los gráficos generales considerados en muchos estudios en análisis de redes . Por ejemplo, la reducción transitiva ofrece una nueva visión 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. [50] Otra técnica esaná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 dado .
Compresión de datos [ editar ]
Los gráficos acíclicos dirigidos también pueden usarse como una representación compacta de una colección de secuencias. En este tipo de aplicación, uno encuentra un DAG en el que las rutas 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 use menos espacio del que se necesitaría para enumerar todas las secuencias por separado. Por ejemplo, el gráfico de palabras acíclicas dirigidas 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 las palabras en inglés. [51]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íclicas dirigidas ahorra espacio sobre un trie al permitir que las rutas diverjan y vuelvan a unirse, de modo que un conjunto de palabras con los mismos sufijos posibles se pueda representar mediante un solo vértice de árbol. [52]
La misma idea de usar un DAG para representar una familia de caminos se produce en el diagrama de decisión binario , [53] [54] una estructura de datos basada en DAG para representar funciones binarias. En un diagrama de decisión binario, cada vértice no hundido 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 siguiendo una ruta, comenzando desde el vértice de origen único, 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íclicas dirigidas se pueden ver como una forma comprimida de intentos, los diagramas de decisión binarios se pueden ver como formas comprimidas de árboles de decisiónque ahorran espacio al permitir que los caminos se reúnan cuando estén de acuerdo con los resultados de todas las decisiones restantes.
Thanks
ResponderEliminarPERT CPM