En computación y teoría de grafos , una estructura de conectividad dinámica es una estructura de datos que mantiene dinámicamente información sobre los componentes conectados de un grafo.
El conjunto V de vértices del gráfico es fijo, pero el conjunto E de aristas puede cambiar. Los tres casos, en orden de dificultad, son:
- Los bordes solo se agregan al gráfico (esto se puede llamar conectividad incremental );
- Los bordes solo se eliminan del gráfico (esto se puede llamar conectividad decremental );
- Los bordes se pueden agregar o eliminar (esto se puede llamar conectividad completamente dinámica ).
Después de cada adición / eliminación de un borde, la estructura de conectividad dinámica debe adaptarse de manera que puede dar respuestas rápidas a las preguntas de la forma "¿hay un camino entre x y y ?" (equivalentemente: "hacer vértices x y y pertenecen a la misma componente conectado?").
Conectividad incremental
Si solo se pueden agregar bordes, entonces el problema de conectividad dinámica se puede resolver mediante una estructura de datos de conjuntos disjuntos . Cada conjunto representa un componente conectado; existe un camino entre x y y si y sólo si pertenecen a la misma serie. El tiempo amortizado por operación es, donde n es el número de vértices y α es la función de Ackermann inversa . [1] [2]
Conectividad decremental
El caso en el que los bordes solo se pueden eliminar fue resuelto por Shimon Even y Yossi Shiloach . [3]
La estructura utiliza una tabla que especifica, para cada vértice, el nombre del componente al que pertenece. Por tanto, una consulta de conectividad lleva un tiempo constante. El desafío es actualizar la tabla cuando se elimina una ventaja.
Gráficos acíclicos (bosques)
Cuando se elimina el borde u - v en un bosque , el árbol que contiene ese borde se divide en dos árboles: uno de ellos contiene u y el otro contiene v . La tabla se actualiza de la siguiente manera.
- Escanee el árbol a partir de u (usando cualquier algoritmo de escaneo de árbol, como DFS ).
- Escanee el árbol a partir de v .
- Realice los dos procedimientos anteriores en paralelo, es decir, utilizando dos procesos paralelos o intercalando sus pasos (haga un paso del primer escaneo, luego un paso del segundo escaneo, luego un paso del primer escaneo, etc.).
- Suponga que el primer escaneo que termina es el escaneo de u (por lo que sabemos que el árbol que contiene u es el más pequeño). Asigne un nuevo nombre de componente a cada nodo del subárbol de u .
Dado que siempre cambiamos el nombre del subcomponente más pequeño, el tiempo amortizado para una operación de eliminación es .
Gráficos generales
Cuando se elimina una arista en un gráfico general, no sabemos si su componente sigue siendo un solo componente (conectado por otras aristas) o se divide en dos componentes. Entonces usamos dos procesos que se ejecutan en paralelo (o de forma intercalada). El proceso A comprueba si la eliminación del borde rompe un componente y, si lo hace, se detienen ambos procesos. El proceso B comprueba si la eliminación del borde no rompe el componente al que pertenece, y si no lo hace, nuevamente ambos procesos se detienen.
- Proceso A
- es similar al caso del gráfico acíclico: hay dos subprocesos que escanean desde ambos extremos del borde eliminado. Si uno de los subprocesos finaliza antes de llegar al otro extremo, esto significa que el componente se divide en dos subcomponentes y el nombre del subcomponente más pequeño se actualiza, como antes. Por lo tanto, el tiempo amortizado para una operación de eliminación vuelve a ser .
- Proceso B
- utiliza una estructura de amplitud primero (BFS), que se inicializa de la siguiente manera. Se elige un vértice r y el BFS parte de él. El único vértice en el nivel 0 es r . Todos los vértices de la distancia i desde la raíz están en el nivel i . Si G no está conectado, se inicia una nueva exploración en algún vértice v no explorado , v se coloca en el nivel 1 y un borde artificial conecta v con la raíz r ; todos los vértices de la distancia i de v están ahora en el nivel i +1, etc. Se introducen aristas artificiales para mantener todos los componentes conectados en una estructura BFS y se utilizan solo para este propósito. Claramente, los bordes artificiales se usan solo en el proceso B.
La estructura tiene las siguientes propiedades. Un vértice v en el nivel i , i > 0, tiene solo tres tipos de aristas: aristas hacia atrás que lo conectan con el nivel i −1 (hay al menos una arista, que puede ser artificial), aristas locales que lo conectan con otras aristas en el nivel i (hay cero o más de tales aristas), o aristas delanteras que lo conectan con las aristas en el nivel i +1 (hay cero o más de tales aristas). Entonces, para cada vértice v , mantenemos tres conjuntos de aristas (hacia atrás, local y hacia adelante).
Cuando un borde u - v se borra, hay dos opciones: o U y V están en el mismo nivel, o que se encuentran en niveles cuyos difiere por el número 1.
- Caso 1
- tanto u como v están en el mismo nivel. En este caso, la eliminación del borde no puede cambiar los componentes. El borde simplemente se elimina de los conjuntos de bordes locales de u y v , y el proceso B se detiene (y, por lo tanto, el proceso A también se detiene). Nuestra estructura BFS sigue siendo válida.
- Caso 2
- U y V están en diferentes niveles. Sin pérdida de generalidad, suponga que u está en el nivel i −1 y v está en el nivel i ; por lo tanto, el borde debe eliminarse de adelante ( u ) y de atrás ( v ).
- Caso 2.1
- Si el nuevo reverso ( v ) no está vacío, entonces los componentes no han cambiado: hay otros bordes que conectan v al revés. El proceso B se detiene (y el proceso A también se detiene).
- Caso 2.2
- Si el nuevo revés ( v ) está vacío, entonces v ya no está conectado al nivel i −1, por lo que su distancia desde la raíz ya no es i ; debe ser al menos i +1. Además, puede haber otros vértices, conectados av , cuya distancia desde la raíz aumenta como resultado de la eliminación. Para calcular las distancias actualizadas, usamos una cola Q, que inicialmente contiene solo el vértice v .
Mientras Q no está vacío:
- w : = quitar de la cola (Q)
- Quite w de su nivel (digamos, j ) y colóquelo en el siguiente nivel ( j +1).
- Actualizar vecinos locales:
- Para cada borde w - x en local ( w ), elimínelo de local ( x ) y colóquelo en forward ( x ).
- al revés ( w ): = local ( w )
- Actualizar vecinos de reenvío:
- Para cada borde w - x en adelante ( w ), quítelo de atrás ( x ) y colóquelo en local ( x ); si el nuevo backward ( x ) está vacío, ponga x en Q.
- local ( w ): = adelante ( w )
- adelante ( w ): = conjunto vacío
- Si el nuevo reverso ( w ) está vacío, vuelva a poner en cola w en Q.
Si la eliminación del borde no rompe ningún componente y estamos en el caso 2.2, eventualmente el procedimiento se detendrá. En este caso, es fácil ver que la estructura BFS se mantiene correctamente. Si su eliminación rompe un componente, el procedimiento no se detendrá por sí solo. Sin embargo, el proceso A, reconociendo la ruptura, se detendrá y ambos procesos se detendrán. En este caso, se ignoran todos los cambios realizados en la estructura BFS y volvemos a la estructura BFS que teníamos justo antes de la eliminación, excepto que el borde eliminado ahora se reemplaza por un borde artificial. Claramente, en este caso v es ahora la raíz de un árbol que incluye el nuevo componente, y quizás componentes adicionales, a través de algunos otros bordes artificiales. También, no hay bordes que conectan los descendientes de v con cualquier vértices que no son v 's descendientes, excepto el borde artificial. [4]
siempre que se procesa un borde en el procedimiento, uno de sus puntos finales cae un nivel. Dado que el nivel más bajo que puede alcanzar un vértice en ejecuciones que terminan con el proceso B es, el costo por borde está limitado por . Por tanto, el tiempo amortizado por operación de borrado es.
Conectividad completamente dinámica
Gráficos acíclicos (bosques)
Un bosque se puede representar utilizando una colección de árboles de Link-cut o árboles de gira de Euler . Entonces, el problema de conectividad dinámica se puede resolver fácilmente, ya que por cada dos nodos x, y, x está conectado ay si y solo si FindRoot (x) = FindRoot (y). El tiempo de actualización amortizado y el tiempo de consulta son ambos O (log ( n )).
Gráficos generales
Un gráfico general se puede representar por su bosque de expansión , un bosque que contiene un árbol para cada componente conectado del gráfico. Llamamos a este bosque que abarca F . La propia F puede estar representada por un bosque de árboles de euler tour .
Las operaciones de consulta y de inserción se implementan utilizando las operaciones correspondientes en los árboles ET representan F . La operación desafiante es Delete y, en particular, la eliminación de un borde que está contenida en uno de los árboles de expansión de F . Esto rompe el árbol de expansión en dos árboles, pero es posible que haya otro borde que los conecte. El desafío es encontrar rápidamente una ventaja de reemplazo, si es que existe. Esto requiere una estructura de datos más compleja. Varias de estas estructuras se describen a continuación.
La estructura de nivel
A cada borde del gráfico se le asigna un nivel . Sea L = lg n . El nivel de cada borde insertado en el gráfico se inicializa en L y puede disminuir hacia 0 durante las operaciones de eliminación.
Para cada i entre 0 y L , defina Gi como el subgrafo que consta de bordes que están en el nivel i o menos, y Fi un bosque de expansión de Gi . Nuestro bosque F de antes ahora se llama FL . Mantendremos una secuencia decreciente de bosques FL ⊇ ... ⊇ F 0. [5] [6]
Operaciones
Las operaciones de consulta e inserción utilizan solo el FL del bosque más grande . Los subgrafos más pequeños se consultan solo durante una operación de eliminación y, en particular, al eliminar un borde que está contenido en uno de los árboles de expansión de FL .
Cuando se elimina un borde e = x - y , primero se elimina de FL y de todos los bosques de expansión más pequeños a los que pertenece, es decir, de cada Fi con i ≥ nivel ( e ). Luego buscamos un borde de reemplazo.
Comience con el bosque de expansión más pequeño que contenga e , es decir, Fi con i = nivel ( e ). El borde e pertenece a un cierto árbol T ⊆ Fi . Después de la eliminación de e , el árbol T se rompe para dos árboles más pequeños: Tx que contiene el nodo x y Ty que contiene el nodo y . Un borde de Gi es un borde de reemplazo, si y solo si conecta un nodo en Tx con un nodo en Ty . Suponga que wlog que Tx es el árbol más pequeño (es decir, contiene como máximo la mitad de los nodos de T ; podemos decir el tamaño de cada subárbol mediante una anotación agregada a los árboles de Euler).
Recorrimos todos los bordes ε con nivel iy al menos un nodo en Tx :
- Si el otro nodo de ε está en Ty , entonces se encuentra un borde de reemplazo. Agregue este borde a Fi y a todos los bosques que lo contengan hasta FL y termine. Los bosques que se extienden son fijos. Tenga en cuenta que para pagar esta búsqueda, disminuimos el nivel de los bordes visitados durante la búsqueda.
- Si el otro nodo de ε está en Tx , entonces este no es un borde de reemplazo, y para 'penalizarlo' por perder nuestro tiempo, disminuimos su nivel en 1.
Análisis
El nivel de cada borde se reducirá como máximo lg n veces. ¿Por qué? Porque con cada disminución, cae en un árbol cuyo tamaño es como máximo la mitad del tamaño de su árbol en el nivel anterior. Entonces, en cada nivel i , el número de nodos en cada componente conectado es como máximo 2 i . Por lo tanto, el nivel de un borde es siempre al menos 0.
Cada borde cuyo nivel disminuye, toma tiempo para encontrar (usando las operaciones del árbol ET). En total, cada borde insertado toma tiempo hasta que se elimine, por lo que el tiempo amortizado para la eliminación es . La parte restante de eliminar también toma tiempo, ya que tenemos que eliminar el borde de como máximo niveles, y eliminar de cada nivel requiere (nuevamente usando las operaciones ET).
En total, el tiempo amortizado por actualización es . El tiempo por consulta se puede mejorar para.
Sin embargo, el peor momento por actualización puede ser . La cuestión de si se puede mejorar el momento del peor de los casos había sido una cuestión abierta, hasta que fue resuelta afirmativamente por la estructura de Cutset.
La estructura de Cutset
Dado un gráfico G (V, E) y un subconjunto T⊆V, defina cutset (T) como el conjunto de bordes que conectan T con V \ T. La estructura de corte es una estructura de datos que, sin mantener todo el gráfico en la memoria, puede encontrar rápidamente un borde en el corte, si tal borde existe. [7]
Empiece dando un número a cada vértice. Suponga que hay n vértices; entonces cada vértice se puede representar por un número con lg ( n ) bits. A continuación, asigne un número a cada borde, que es una concatenación de los números de sus vértices, un número con 2 lg ( n ) bits.
Para cada vértice v , calcule y mantenga xor ( v ), que es el xor de los números de todos los bordes adyacentes a él.
Ahora, para cada subconjunto T⊆V, es posible calcular xor (T) = el xor de los valores de todos los vértices en T. Considere una arista e = u - v que es una arista interna de T (es decir, tanto u como v están en T). El número de e se incluye dos veces en xor (T): una vez para u y una vez para v . Dado que el xor de cada número consigo mismo es 0, e desaparece y no afecta a xor (T). Por lo tanto, xor (T) es en realidad el xor de todos los bordes en cutset (T). Hay varias opciones:
- Si xor (T) = 0, entonces podemos responder con confianza que cutset (T) está vacío.
- Si xor (T) es el número de una arista real e , entonces probablemente e sea la única arista en el corte (T), y podemos devolver e . También podemos leer los puntos finales de e a partir del número de e dividiéndolo en los bits lg ( n ) más a la izquierda y los bits lg ( n ) más a la derecha.
- La tercera opción es que xor (T) es un número distinto de cero que no representa una ventaja real. Esto solo puede suceder si hay dos o más aristas en cutset (T), ya que en ese caso xor (T) es el xor de varios números de aristas. En este caso, informamos "falla", ya que sabemos que hay bordes en el conjunto de cortes pero no podemos identificar ningún borde individual. [8]
Nuestro objetivo ahora es manejar esta tercera opción.
Primero, cree una secuencia de niveles lg ( n ) de las estructuras cortadas, cada una de las cuales contiene aproximadamente la mitad de los bordes del nivel superior (es decir, para cada nivel, elija cada borde del nivel superior con probabilidad 1/2). Si en el primer nivel xor (T) devuelve un valor ilegal, lo que significa que cutset (T) tiene dos o más aristas, entonces existe la posibilidad de que en el siguiente nivel, que contiene menos aristas, xor (T) devuelva un valor legal valor ya que cutset (T) contendrá un solo borde. Si xor (T) todavía devuelve un valor ilegal, continúa al siguiente nivel, etc. Dado que el número de aristas está disminuyendo, hay dos casos:
- El buen caso es que finalmente encontramos un nivel en el que cutset (T) contiene un solo borde; luego devolvemos ese borde y terminamos.
- El mal caso es que finalmente encontramos un nivel en el que cutset (T) no contiene bordes; luego informamos "falla", ya que sabemos que hay bordes en el conjunto de cortes pero no podemos identificar ningún borde individual.
Es posible demostrar que la probabilidad de éxito es de al menos 1/9.
A continuación, cree una colección de versiones independientes de C lg ( n ) de la estructura de niveles, donde C es una constante. En cada versión, realice una reducción aleatoria independiente de los bordes de un nivel a otro. Pruebe cada consulta en cada una de las versiones hasta que una de ellas tenga éxito. La probabilidad de que todas las versiones fallen es como máximo:
Mediante la selección adecuada de C podemos hacer que la probabilidad de falla se acerque arbitrariamente a 0.
Operaciones
Podemos agregar una estructura cortada a una estructura de conectividad dinámica.
Las operaciones Insertar y Eliminar en la estructura del conjunto de cortes se realizan exactamente de la misma manera: el borde insertado / eliminado se XORed en ambos puntos finales.
Cuando se elimina un borde del bosque de expansión utilizado para la estructura de conectividad dinámica, la estructura de corte se utiliza para encontrar un borde de reemplazo.
Análisis
Una sola estructura de conjunto de cortes requiere solo O ( n lg n ) de memoria, solo un solo número, con 2 lg n bits, para cada uno de los n vértices. No tenemos que mantener los bordes en sí mismos. Para gráficos densos, esto es mucho más económico que mantener el gráfico completo en la memoria.
Tenemos que mantener las versiones de lg ( n ), cada una de las cuales contiene niveles de lg ( n ). Por lo tanto, el requisito de memoria total es.
El tiempo de consulta es O (polylog ( n )) en el peor de los casos. Esto contrasta con la estructura The Level , en la que el tiempo de consulta es O (polylog ( n )) amortizado, pero el tiempo del peor de los casos es O ( n ).
Conectividad dinámica sin conexión
Si el orden en el que se eliminarán los bordes se conoce de antemano, entonces podemos resolver el problema de conectividad dinámica en log (n) por consulta. Si podemos mantener un Bosque de expansión máximo donde los bordes están ordenados por su tiempo de eliminación, sabemos que cuando eliminamos algún borde que está en el bosque, no hay ningún borde posible que pueda reemplazarlo. Si hubiera algún borde que conecta los mismos dos componentes que lo hace el borde eliminado, entonces este otro borde habría sido parte del bosque de expansión máxima en lugar del borde que eliminamos. Esto hace que la operación de eliminación sea trivial: simplemente necesitamos dividir el árbol en sus dos partes si el borde a eliminar es parte de nuestro bosque, o ignorar la operación de lo contrario.
Agregar un borde es un poco más complicado. Si agregamos un borde e de u a v, entonces si uyv no están conectados, entonces este borde será parte del bosque de expansión máxima. Si están conectados, queremos agregar u-> v a nuestro bosque si puede mejorar nuestro Bosque de expansión máxima. Para hacer esto, necesitamos verificar rápidamente qué borde tiene el menor tiempo de eliminación en la ruta de u a v. Si el tiempo de eliminación de este borde es posterior al tiempo de eliminación de e, entonces e no puede mejorar nuestro bosque de expansión mínimo. De lo contrario, el otro borde debe eliminarse y reemplazarse con e.
Esto requiere que hagamos las siguientes operaciones: agregar un borde, cortar un borde y consultar el borde mínimo en una ruta que se puede hacer con bastante facilidad con un árbol de corte de enlace en log (n) por operación.
Ver también
Referencias
- ^ Tarjan, Robert Endre (1975). "Eficiencia de un algoritmo de unión de conjuntos bueno pero no lineal". Revista de la ACM . 22 (2): 215–225. CiteSeerX 10.1.1.399.6704 . doi : 10.1145 / 321879.321884 .
- ^ Tarjan, Robert Endre (1979). "Una clase de algoritmos que requieren un tiempo no lineal para mantener conjuntos disjuntos" . Revista de Ciencias de la Computación y Sistemas . 18 (2): 110-127. doi : 10.1016 / 0022-0000 (79) 90042-4 .
- ^ Shiloach, Y .; Incluso, S. (1981). "Un problema de eliminación de bordes en línea". Revista de la ACM . 28 : 1–4. doi : 10.1145 / 322234.322235 .
- ^ Una forma de realizar el regreso a la estructura anterior a la eliminación de e sin tener que copiar toda la estructura es mantener en una pila todos los cambios que tuvieron lugar en la estructura BFS desde la eliminación de e y deshacerlos uno por uno. De esta forma, el tiempo de procesamiento solo se multiplica por una constante.
- ^ Holm, J .; De Lichtenberg, K .; Thorup, M. (2001). "Algoritmos polilogarítmicos deterministas totalmente dinámicos para conectividad, árbol de expansión mínimo, 2 bordes y biconnectividad". Revista de la ACM . 48 (4): 723. doi : 10.1145 / 502090.502095 .
- ^ Problemas de gráficos dinámicos - en notas de clase en estructuras de datos avanzadas. Prof. Erik Demaine; Escriba: Katherine Lai.
- ^ Kapron, BM; King, V .; Mountjoy, B. (2013). Conectividad de gráficos dinámicos en el peor de los casos polilogarítmicos . Actas del Vigésimo Cuarto Simposio Anual ACM-SIAM sobre Algoritmos Discretos. pag. 1131. doi : 10.1137 / 1.9781611973105.81 . ISBN 978-1-61197-251-1.
- ^ Existe una pequeña probabilidad de que el xor de varias aristas diferentes dé como resultado un número que resulta ser el número de otra arista. Esto podría dar lugar a un falso positivo. Para reducir la probabilidad de este evento, podemos ampliar el dominio de los números de vértices a, digamos, n 3 en lugar de n . Entonces, si hay más de un borde en el cutset (T), es casi seguro que xor (T) será un valor sin sentido, como se indicó anteriormente.
- Ver también: Thorup, M. (2000). Conectividad de gráficos totalmente dinámica casi óptima . Actas del trigésimo segundo simposio anual de ACM sobre teoría de la computación - STOC '00. pag. 343. doi : 10.1145 / 335305.335345 . ISBN 1581131844.