PROFILBARU.COM

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 $O(\alpha (n))$ , 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.^[1]

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 $O(\log(n))$ .

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 $O(\log(n))$ .

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.^[2]

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 $O(n)$ .

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 $O(\lg n)$ tiempo para encontrar (utilizando las operaciones del árbol ET).En total, cada arista insertada toma $O(\lg ^{2}n)$ tiempo hasta que es eliminada, así que el tiempo amortizado para la elimiación es $O(\lg ^{2}n)$ . La parte restante de eliminar también toma $O(\lg ^{2}n)$ , ya que tenemos que eliminar la arista de como máximo $O(\lg n)$ niveles, y eliminando de cada nivel toma $O(\lg n)$ (otra vez utilizando las operaciones del árbol ET). En total, el tiempo amortizado por actualización es $O(\lg ^{2}n)$ . Los tiempos por consulta pueden ser mejorados a $O(\lg n/\lg \lg n)$ .

Aun así, el tiempo del caso peor por actualización podría ser $O(n)$ . La cuestión de si los tiempos del caso peor pueden ser mejorados había sido una cuestión abierta, hasta que fue solucionado por la estructura "Cutset".

La estructura Cutset

Dado un grafo G(V,E) y un subconjunto T⊆V, definimos cutset(T) como el conjunto de aristas que conecta T con V\T. El cutset es una estructura de datos que, sin mantener el grafo entero en memoria, puede encontrar deprisa una arista en el cutset, si tal arista existe.^[3]

Empezamos por dar un número a cada vértice. Suponer que hay n vértices; entonces cada vértice puede ser representado por un número con lg(n) bits. Luego, dar un número a cada arista, el cual es una concatenación de los números de sus vértices - un número con 2lg(n) bits.

Para cada vértice v, calcula y mantener xor(v), el cual es el xor de los números de todos las aristas adyacentes a él.

Ahora para cada subconjunto T⊆V, es posible de calcular xor(T) = el xor de los valores de todos los vértices en T. Considerar una arista e = u-v cuál es una arista interna de T (i.e. ambos u y v están en T). El número de e está incluido dos veces en xor(T) - una vez para u y una vez para v. Ya que el xor de cada número con él es 0, e desaparece y no afecta al xor(T). Así, xor(T) es de hecho el xor de todas las aristas en cutset(T). Hay varias opciones:

Si xor(T)=0, entonces confiadamente podemos responder que cutset(T) es vacío.
Si xor(T) es el número de una arista real e, entonces probablemente e es la unica arista en cutset(T), y podemos retornar e. Podemos también leer los extremos de e del número de e por partirlo los lg(n) bits más a la izquierda los lg(n) bits más a la derecha.
La tercera opción es que xor(T) es un número distinto de cero el cual no representa una arista. Esto solo puede pasar si hay dos o más aristas en cutset(T), esto significa que xor(T) es el xor de varios números de aristas. En este caso, informamos "fracaso", ya que sabemos que hay aristas en el cutset pero no puede ser identificada una sola arista.^[4]

Nuestro objetivo ahora es manejar esta tercera opción.

Primero, crear una secuencia de lg(n) niveles de las estructuras cutset, cada cual contiene sobre la mitad de las aristas del nivel superior (i.e., para cada nivel, selecciona cada arista del nivel superior con probabilidad 1/2). Si en el primer nivel xor(T) regresa un valor ilegal, significando que cutset(T) tiene dos o más aristas, entonces hay una posibilidad que en el nivel próximo, el cual contiene menos aristas, xor(T) regresará un valor legal ya cutset(T) contendrá una sola arista. Si xor(T) todavía regresa un valor ilegal, continúa al nivel próximo, etc. Como el número de aristas va en decrecimiento, hay dos casos:

El caso bueno es que finalmente encontramos un nivel en el que cutset(T) contiene una sola arista; entonces retornamos la arista y finalizamos.
El caso malo es que finalmente encontramos un nivel en que cutset(T) no contiene ninguna arista; entonces informamos "fracaso", ya que sabemos que hay aristas en el cutset pero no puede identificar una única.

Es posible de probar que la probabilidad de éxito es al menos 1/9.

Luego, crear una colección de Clg(n) versiones independientes de la estructura de nivel, donde C es una constante. En cada versión, hacer una reducción aleatoria independiente de bordes de nivel a nivel. Probar cada consulta en cada una de las versiones hasta que una de ellas tiene éxito. La probabilidad de que todas las versiones fallan es como máximo:

(1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}

Por selección apropiada de C podemos hacer la probabilidad del fracaso arbitrariamente cercana a 0.

Operaciones

Podemos añadir una estructura cutset a una estructura de conectividad dinámica.

Las operaciones de Insertar y Eliminar en la estructura cutset están hecha en exactamente la misma manera: la arista insertada/eliminada es XOReada a ambos de sus extremos.

Cuándo una arista es eliminada del bosque abarcador utilizado para la estructura de conectividad dinámica, el cutset suele encontrar una arista de sustitución.

Análisis

Una sola estructura cutset requiere O(n lg n) memoria - un único número, con 2 lg n bits, para cada uno de los n vértices. No tenemos que mantener las aristas. Para grafos densos, esto es mucho más barato que manteniendo el grafo entero en memoria.

Tenemos que mantener lg(n) versiones, cada cual contiene lg(n) niveles. De ahí, el requisito de memoria total es O(n lg^3 n).

El tiempo de consulta es O(polylog(n)) en el caso peor. Esto es en contraste a #La estructura de Nivel, en qué el tiempo de consulta es O(polylog(n)) amortizado, pero el tiempo peor es O(n).

Referencias

↑ Shiloach, Y.; Even, S. (1981). «An On-Line Edge-Deletion Problem». Journal of the ACM 28: 1. doi:10.1145/322234.322235.
↑ 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.
↑ Kapron, B. M.; King, V.; Mountjoy, B. (2013). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. ISBN 978-1-61197-251-1. doi:10.1137/1.9781611973105.81.
↑ There is a small probability that the xor of several different edges will result in a number which happens to be the number of another edge. This might lead to a false positive. In order to reduce the probability of this event, we can enlarge the domain of the numbers of vertices to, say, n³ instead of n. Then, if there is more than one edge in cutset(T), xor(T) will almost certainly be a meaningless value, as stated above.

Ve también: Thorup, M. (2000). Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. ISBN 1581131844. doi:10.1145/335305.335345.

Datos: Q20018775

[1] Shiloach, Y.; Even, S. (1981). «An On-Line Edge-Deletion Problem». Journal of the ACM 28: 1. doi:10.1145/322234.322235.

[2] 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.

[3] Kapron, B. M.; King, V.; Mountjoy, B. (2013). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. ISBN 978-1-61197-251-1. doi:10.1137/1.9781611973105.81.

[4] There is a small probability that the xor of several different edges will result in a number which happens to be the number of another edge. This might lead to a false positive. In order to reduce the probability of this event, we can enlarge the domain of the numbers of vertices to, say, n³ instead of n. Then, if there is more than one edge in cutset(T), xor(T) will almost certainly be a meaningless value, as stated above.

[1]

[2]

[3]

[4]