En computación y teoría de grafos, una estructura de conectividad dinámica es una estructura de datos que dinámicamente mantiene información sobre las componentes conexas de un grafo.
El conjunto V de vértices del grafo está fijado, pero el conjunto E de las aristas pueden cambiar. Los tres casos, por orden de dificultad, son: Las aristas son solo añadidas al grafo (esto se puede llamar conectividad incremental); Las aristas son solo eliminadas del grafo (esto se puede llamar conectividad decremental); Las aristas pueden ser añadidas o eliminadas (esto se puede llamar conectividad dinámica completa). Después de cada adición/eliminación de una arista, la estructura de conectividad dinámica se tendría que adaptar tal que pueda dar respuestas rápidas a las consultas de la forma "existe camino entre x e y?" (equivalente: "x e y pertenecen a la misma componente conexa?").
Conectividad incremental Si las aristas solo pueden ser añadidos, entonces el problema de conectividad dinámico puede ser solucionado con un conjunto disjunto. Cada conjunto representa un componente conectado; existe camino entre x e y si y solo si pertenecen al mismo conjunto. El tiempo amortizado por operación es , donde n es el número de vértices y α es la inversa de la función de Ackermann, el cual es casi constante.
El caso en las aristas solo pueden ser eliminadas fue resuelto por Shimon Even y Yossi Shiloach.
La estructura utiliza una tabla que especifica, para cada vértice, el nombre de la componente a la que pertenece. Por lo tanto una consulta de conectividad toma tiempo constante. El reto es actualizar la tabla cuando la arista es eliminada.
Grafos Acíclicos (bosques) Cuando la arista u-v es eliminada en un bosque, el árbol que contiene esa arista es roto en dos árboles: uno de ellos contiene u y el otro contiene v. La tabla es actualizada de la manera siguiente. Recorrer el árbol empezando por u (utilizando cualquier algoritmo de recorrido, como DFS). Recorrer el árbol empezando por v. Hacer lo anterior utilizando dos procedimientos en paralelo, i.e., ya sea utilizando dos procesos paralelos, o intercalando sus pasos (marca un paso de primer recorrido, entonces un paso del segundo, entonces un paso del prime, etc.). Suponer el primer recorrido que termina es el de u (así que sabemos que el árbol que contiene u es el más pequeño). Asignar un nombre de componente nuevo a cada nodo en el subárbol de u. Como siempre renombramos la componente más pequeña, el tiempo amortizado para la operación de eliminar es .
Grafos generales Cuándo una arista es eliminada en un grafo general, no sabemos si su componente queda conectada por otras aristas o es separada en dos componentes. Así que utilizamos dos procesos en paralelo (o intercalando). El proceso A controla si la eliminación de la arista rompe la componente, y si lo hace, ambos procesos paran. El proceso B controla si la eliminación de la arista no rompe la componente al cual pertenece, y si no lo hace, otra vez ambos procesos paran.
Proceso A es similar al caso del grafo acíclico: hay dos sub-procesos que recorren a partir de ambos vértices que une la arista. Si uno de los sub-procesos termina antes de llegar al otro extremo, esto significa que la componente está rota en dos sub-componentes, y el nombre de la sub-componente más pequeña es actualizado, como antes. Por ello el tiempo amortizado para eliminar es otra vez .
Proceso B utiliza una estructura "primero a lo ancho" (BFS), la cual es inicializada de la siguiente forma. Un vértice r es escogido y el BFS empieza desde él. El único vértice en el nivel 0 es r. Todos los vértices de distancia i de la raíz están en el nivel i. Si G no es conexo, se comienza un nuevo recorrido desde cualquier vértice v no visitado, v es puesto en el nivel 1, y una arista artificial es conectada de v a la raíz r; todos los vértices a distancia i de v están ahora en el nivel i+1, etc. Las aristas artificiales son introducidas para mantener todas las componentes conexas en una sola estructura BFS y serán utilizadas solo para este propósito. Claramente, las aristas artificiales están utilizadas 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 de retroceso, que conectan este al nivel i-1 (hay al menos una de estas aristas, la cual puede ser artificial); aristas locales, que conectan este con otras aristas en el nivel i( hay cero o más de estas aristas); o aristas de adelanto, que conectan este al nivel i+1 (hay cero o más de estas aristas). Entonces para cada vértice v, mantenemos tres conjuntos de aristas (retroceso, local y adelanto).
Cuándo una arista u-v es eliminada, hay dos opciones: ya sea u o v están en el mismo nivel, o en niveles que difieren por uno.
Caso 1: ambos u y v están en el mismo nivel. En este caso, la eliminación de aristas no puede cambiar las componentes. La arista es eliminada de los conjuntos de aristas locales de u y v, y el proceso B para (y por tanto el proceso A se detiene también). Nuestra estructura BFS es todavía válida.
Caso 2: u y v están en niveles diferentes. W.l.o.g, asume que u está en el nivel i-1 y v en el nivel i; por ello el borde tendría que ser eliminado de adelante(u) y de retroceso(v).
Caso 2.1: Si el nuevo retroceso(v) no es vacío, entonces las componentes no han cambiado: hay otras aristas que conectan v en retroceso. Proceso B para (y proceso A también).
Caso 2.2: Si el nuevo retroceso(v) es vacío, entonces v ya no está conectado al nivel i-1, y así su distancia a la raíz ya no es i; tiene que ser al menos i+1. Además, puede haber otros vértices, conectados a v, cuya distancia a la raíz aumenta como resultado de la eliminación. Para actualizar las distancias, utilizamos un cola Q, la cual inicialmente contiene solo el vértice v.
Mientras Q no está vacía: w := dequeue(Q) Saca w de su nivel (j), y ponerlo en nivel próximo (j+1). Actualizar los vecinos: Para cada arista w-x en local(w), removerla de local(x) e insertarla en adelante(x). retroceso(w) := local(w) Actualizar vecinos adelante: Para cada arista w-x en adelante(w), removerla de retroceso(x) e insertarla en local(x); si el nuevo retroceso(x) es vacío, encolar x en Q. local(w) := adelante(w) adelante(w) := conjunto vacío Si el nuevo retroceso(w) es vacío, encola w otra vez en Q. Si la eliminación de aristas no rompe cualquier componente y estamos en el caso 2.2, entonces en algún momento el procedimiento parará. En este caso es fácil de ver que la estructura BFS es mantenida correctamente. Si su eliminación rompe un componente, entonces el procedimiento no parará por él mismo. Aun así, el proceso A, reconociendo la interrupción, parará, y ambos procesos pararán. En este caso todos los cambios hechos a la estructura BFS son ignorados, y volvemos a la estructura BFS que teníamos antes de la eliminación, exceptuando que la arista eliminada es ahora una arista artificial. Claramente, en este caso v es ahora la raíz de un árbol qué incluye el componente nuevo, y quizás componentes adicionales, a través de algunas otras aristas artificiales. También, no hay ninguna arista conectando los descendientes de v con cualesquier vértices qué no es descendiente de v, excepto la arista artificial u-v.One way to realize the return to the structure preceding the deletion of e without having to copy the whole structure is to keep on a stack all the changes that took place in the BFS structure since the deletion of e and undo them one by one. This way the processing time is only multiplied by a constant.
Siempre que una arista es procesada en el procedimiento, uno de su extremos disminuye un nivel. Dado que el vértice de nivel más bajo es |V|-1, el coste por arista es acotado por 2|V|. Por ello el tiempo amortizado para la operación de eliminación es .
Conectividad dinámica completa
Grafos Acíclicos (bosques) Un bosque puede ser representado utilizando una colección de ya sea "Link-cut trees" o "Euler tour trees". Entonces el problema de conectividad dinámico puede ser solucionado fácilmente, para cada dos nodos x,y, x está conectado a y si y solo si FindRoot(x)=FindRoot(y). Los tiempos de actualización amortizados y tiempo de consulta son ambos O(log(n)).
Grafos generales Un grafo general puede ser representado por su bosque abarcador - un bosque que contiene un árbol para cada componente. Llamamos a este bosqueF. F puede ser representado por un bosque de "Euler tour trees".
Las operaciones de consulta e inserción son implementadas utilizando las operaciones correspondientes en los árboles del ET que representan a F. La operación que es un reto es la de eliminación, y en particular, eliminando una arista qué está contenido en uno de los árboles abarcador de F. Esto rompe el árbol en dos árboles, pero, es posible que exista otra arista que los conecta. El reto es encontrar de manera rápida tal arista de sustitución, si existe. Esto requiere una estructura de datos más compleja. Muchas de estas estructuras están descritas más abajo.
La estructura de Nivel Cada arista en el grafo le es asignado un nivel. Dejado L=lg n. El nivel de cada arista insertada al grafo es inicializado a L, y puede disminuir a 0 durante operaciones de eliminación.
Para cada i entre 0 y L, define Gi como el subgrafo constando de las aristas que son de nivel i o menos, y Fi un bosque abarcador de Gi. Nuestro bosque F es ahora llamado FL. Mantendremos una secuencia de decrecimiento de bosques FL ⊆ ... ⊆ F0.
Operaciones Las operaciones de consulta e inserción utilizan solo el bosque más grande FL. Los subgrafos más pequeños son consultados solo durante la operación de eliminar, y en particular, eliminando una arista qué está contenida en uno de los árboles abarcador de FL.
Cuándo tal arista e = x-y es eliminada, es primero sacada de FL y de todos los bosques abarcadores más pequeños al que pertenece, i.e. de cada Fi con i≥nivel(e). Entonces buscamos una arista de sustitución.
Empezar con el bosque abarcador más pequeño que contiene e, concretamente, Fi con i=nivel(e). La arista e pertenece a un árbol T⊆Fi. Después de la eliminación de e, el árbol T se rompe 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 de sustitución, si y solo si conecta un nodo en Tx con un nodo en Ty. Supongamos que Tx es el árbol más pequeño (i.e. contiene como máximo la mitad de los nodos de T; podemos decir la medida de cada subtree por una anotación añadida a los "Euler trees").
Recorremos todas las ariatas ε con nivel i y al menos un nodo en Tx: Si el otro nodo de ε está en Ty, entonces una arista de sustitución ha sido encontrada! Añadir esta arista a Fi y a todos los bosques hasta FL, y termina. Los bosques abarcadores están fijos. Si el otro nodo de ε es en Tx, entonces esto no es una arista de sustitución, y la 'penalizamos' por malgastar nuestro tiempo, disminuyendo su nivel por 1.
Análisis El nivel de cada borde será decrementado como máximo lg n tiempo. Por qué? Porque con cada disminución, cae a un árbol cuya medida es como máximo la mitad de la medida de su árbol en el nivel anterior. Entonces en cada nivel i, el número de los nodos en cada componente conectado es como máximo 2^i. Por ello el nivel de una arista es siempre al menos 0.
Cada arista cuyo nivel es decrementado toma tiempo para encontrar (utilizando las operaciones del árbol ET).En total, cada arista insertada toma tiempo hasta que es eliminada, así que el tiempo amortizado para la elimiación es . La parte restante de eliminar también toma , ya que tenemos que eliminar la arista de como máximo niveles, y eliminando de cada nivel toma (otra vez utilizando las operaciones del árbol ET). En total, el tiempo amortizado por actualización es . Los tiempos por consulta pueden ser mejorados a .