En informática 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 grafo es fijo, pero el conjunto E de aristas puede cambiar. Los tres casos, en orden de dificultad, son:
Después de cada adición o eliminación de un borde, la estructura de conectividad dinámica debe adaptarse de manera tal que pueda dar respuestas rápidas a consultas del tipo "¿hay un camino entre x e y ?" (equivalentemente: "¿los vértices x e y pertenecen al mismo componente conectado?").
Si sólo se pueden añadir aristas, entonces el problema de conectividad dinámica se puede resolver mediante una estructura de datos de conjunto disjunto . Cada conjunto representa un componente conectado; existe un camino entre x e y si y sólo si pertenecen al mismo conjunto. El tiempo amortizado por operación es , donde n es el número de vértices y α es la función inversa de Ackermann . [1] [2]
El caso en el que sólo se pueden eliminar los bordes 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 lo tanto, una consulta de conectividad lleva un tiempo constante. El desafío es actualizar la tabla cuando se elimina una arista.
Cuando se elimina la arista u - v en un bosque , el árbol que contiene esa arista se divide en dos árboles: uno de ellos contiene u y el otro contiene v . La tabla se actualiza de la siguiente manera.
Como siempre cambiamos el nombre del subcomponente más pequeño, el tiempo amortizado para una operación de eliminación es .
Cuando se elimina una arista en un grafo general, no sabemos si su componente permanece como un solo componente (conectado por otras aristas) o se divide en dos componentes. Por lo tanto, utilizamos dos procesos que se ejecutan en paralelo (o de forma intercalada). El proceso A verifica si la eliminación de la arista rompe un componente y, si lo hace, ambos procesos se detienen. El proceso B verifica si la eliminación de la arista no rompe el componente al que pertenece y, si no lo hace, nuevamente ambos procesos se detienen.
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 al nivel i −1 (hay al menos una arista de este tipo, que puede ser artificial), aristas locales que lo conectan a otras aristas en el nivel i (hay cero o más aristas de este tipo), o aristas hacia adelante que lo conectan a aristas en el nivel i +1 (hay cero o más aristas de este tipo). Entonces, para cada vértice v , mantenemos tres conjuntos de aristas (hacia atrás, local y hacia adelante).
Cuando se elimina una arista u - v , hay dos opciones: o u y v están en el mismo nivel, o están en niveles cuyo número difiere en 1.
Mientras Q no esté vacío:
Si la eliminación de la arista no rompe ningún componente y estamos en el caso 2.2, entonces 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, entonces el procedimiento no se detendrá por sí mismo. Sin embargo, el proceso A, reconociendo la ruptura, se detendrá, y ambos procesos se detendrán. En este caso todos los cambios hechos en la estructura BFS son ignorados, y volvemos a la estructura BFS que teníamos justo antes de la eliminación, excepto que la arista eliminada ahora es reemplazada por una arista 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 algunas otras aristas artificiales. Además, no hay aristas que conecten los descendientes de v con ningún vértice que no sea descendiente de v , excepto la arista artificial . [4]
Siempre que se procesa una arista en el procedimiento, uno de sus puntos finales desciende 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 arista está limitado por . Por lo tanto, el tiempo amortizado por operación de eliminación es .
Un bosque se puede representar mediante una colección de árboles de corte de enlaces o árboles de Euler Tour . Entonces, el problema de conectividad dinámica se puede resolver fácilmente, ya que para cada dos nodos x,y, x está conectado a y si y solo si FindRoot(x)=FindRoot(y). El tiempo de actualización amortizado y el tiempo de consulta son ambos O(log( n )).
Un gráfico general se puede representar mediante su bosque de expansión , un bosque que contiene un árbol para cada componente conectado del gráfico. A este bosque de expansión lo llamamos F . F a su vez se puede representar mediante un bosque de árboles de Euler .
Las operaciones de consulta e inserción se implementan utilizando las operaciones correspondientes en los árboles ET que representan a F. La operación más complicada es la de eliminar y, en particular, la de eliminar una arista que se encuentra en uno de los árboles de expansión de F. Esto divide el árbol de expansión en dos árboles, pero es posible que exista otra arista que los conecte. El desafío es encontrar rápidamente una arista de reemplazo, si existe. Esto requiere una estructura de datos más compleja. A continuación se describen varias de estas estructuras.
A cada arista del gráfico se le asigna un nivel . Sea L = lg n . El nivel de cada arista insertada 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 , definamos Gi como el subgrafo que consiste en aristas que están en el nivel i o menor, y Fi como 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]
Las operaciones de consulta e inserción utilizan únicamente el bosque más grande FL . Los subgrafos más pequeños se consultan únicamente durante una operación de eliminación y, en particular, al eliminar una arista que se encuentra en uno de los árboles de expansión de FL .
Cuando se elimina una arista e = x − y , primero se la 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 una arista de reemplazo.
Comience con el bosque de expansión más pequeño que contenía e , es decir, Fi con i = nivel ( e ). La arista e pertenece a un cierto árbol T ⊆ Fi . Después de la eliminación de e , el árbol T se divide en dos árboles más pequeños: Tx que contiene el nodo x y Ty que contiene el nodo y . Una arista de Gi es una arista de reemplazo, si y solo si conecta un nodo en Tx con un nodo en Ty . Supongamos que Tx es el árbol más pequeño (es decir, contiene como máximo la mitad de los nodos de T ; podemos saber el tamaño de cada subárbol mediante una anotación agregada a los árboles de Euler).
Primero disminuimos el nivel de cada borde de Tx en 1. Luego recorremos todos los bordes ε con nivel i y al menos un nodo en Tx :
El nivel de cada arista se reducirá como máximo lg n veces. ¿Por qué? Porque con cada reducción, cae en un árbol cuyo tamaño es como máximo la mitad del tamaño de su árbol en el nivel anterior. Por lo tanto, 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 una arista siempre es como mínimo 0.
Cada arista cuyo nivel se reduce, lleva tiempo para encontrarlo (usando las operaciones del árbol ET). En total, cada arista insertada lleva tiempo hasta que se elimina, por lo que el tiempo amortizado para la eliminación es . La parte restante de la eliminación también lleva tiempo, ya que tenemos que eliminar la arista de la mayoría de los niveles, y eliminar de cada nivel lleva (nuevamente usando las operaciones ET).
En total, el tiempo amortizado por actualización es de . El tiempo por consulta se puede mejorar a .
Sin embargo, el tiempo por actualización en el peor de los casos podría ser de . La cuestión de si se puede mejorar el tiempo en el peor de los casos había sido una pregunta abierta, hasta que la estructura Cutset la resolvió afirmativamente.
Dado un grafo G(V,E) y un subconjunto T⊆V, defina cutset(T) como el conjunto de aristas que conectan T con V\T. La estructura cutset es una estructura de datos que, sin mantener todo el grafo en la memoria, puede encontrar rápidamente una arista en el cutset, si dicha arista existe. [7]
Comience por asignar un número a cada vértice. Supongamos que hay n vértices; entonces, cada vértice puede representarse mediante un número con lg( n ) bits. A continuación, asigne un número a cada arista, 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. Consideremos 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 para u y otra para v . Como el xor de cada número consigo mismo es 0, e se anula y no afecta a xor(T). Por lo tanto, xor(T) es en realidad el xor de todas las aristas en cutset(T). Hay varias opciones:
Nuestro objetivo ahora es abordar esta tercera opción.
Primero, crea una secuencia de lg( n ) niveles de las estructuras cutset, cada uno de los cuales contiene aproximadamente la mitad de las aristas del nivel superior (es decir, para cada nivel, elige cada arista 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 ya que cutset(T) contendrá una sola arista. Si xor(T) aún devuelve un valor ilegal, continúa al siguiente nivel, etc. Dado que la cantidad de aristas está disminuyendo, hay dos casos:
Es posible demostrar que la probabilidad de éxito es al menos 1/9.
A continuación, cree una colección de C lg( n ) versiones independientes 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 sea arbitrariamente cercana a 0.
Podemos agregar una estructura de corte a una estructura de conectividad dinámica.
Las operaciones de inserción y eliminación en la estructura cutset se realizan exactamente de la misma manera: el borde insertado/eliminado se combina con XOR en ambos puntos finales.
Cuando se elimina un borde del bosque de expansión utilizado para la estructura de conectividad dinámica, se utiliza la estructura de corte para encontrar un borde de reemplazo.
Una estructura de cutset única requiere solo O ( n lg n ) de memoria: solo un único número, con 2 lg n bits, para cada uno de los n vértices. No tenemos que mantener los bordes mismos. Para gráficos densos, esto es mucho más económico que mantener el gráfico completo en la memoria.
Tenemos que mantener lg( n ) versiones, cada una de las cuales contiene lg( n ) niveles. Por lo tanto, el requerimiento total de memoria es .
El tiempo de consulta es O (polylog( n )) en el peor de los casos. Esto contrasta con la estructura de nivel, en la que el tiempo de consulta es O (polylog( n )) amortizado, pero el tiempo en el peor de los casos es O ( n ).
Si el orden en el que se eliminarán las aristas se conoce de antemano, podemos resolver el problema de conectividad dinámica a tiempo por consulta. Si podemos mantener un bosque de máxima expansión donde las aristas se ordenan por su tiempo de eliminación, sabemos que cuando eliminamos alguna arista que está en el bosque, no hay ninguna arista posible que pueda reemplazarla. Si hubiera alguna arista que conectara los mismos dos componentes que la arista eliminada, entonces esta otra arista habría sido parte del bosque de máxima expansión en lugar de la arista que eliminamos. Esto hace que la operación de eliminación sea trivial: simplemente necesitamos dividir el árbol en sus dos partes si la arista que se eliminará es parte de nuestro bosque, o ignorar la operación en caso contrario.
Añadir una arista es un poco más complicado. Si añadimos una arista e de u a v, entonces si u y v no están conectadas, esta arista será parte del bosque de máxima expansión. Si están conectadas, queremos añadir u->v a nuestro bosque si puede mejorar nuestro bosque de máxima expansión. Para ello, necesitamos comprobar rápidamente qué arista tiene el menor tiempo de eliminación en la ruta de u a v. Si el tiempo de eliminación de esta arista es posterior al tiempo de eliminación de e, entonces e no puede mejorar nuestro bosque de máxima expansión. De lo contrario, la otra arista debe eliminarse y reemplazarse por e.
Esto requiere que hagamos las siguientes operaciones: agregar un borde, cortar un borde y consultar el borde mínimo en una ruta, lo que se puede hacer con bastante facilidad con un árbol de corte de enlace en log(n) por operación.
