Usuario:Ernest930620/Dynamic connectivity

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 sólo añadidas al grafo (esto se puede llamar conectividad incremental);
• Las aristas son sólo 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 sólo 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 sólo si pertenecen al mismo conjunto. El tiemp${\displaystyle }$o amortizado por operación es $O(\alpha (n))$ , donde n es el número de vértices y α ${\displaystyle }$ es la inversa de la función de Ackermann, el cual es casi constante.${\displaystyle }$

El caso en las aristas sólo pueden ser eliminadas fue resuelto por Shimon Incluso 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 utlizando 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 subarbol de u.

como siempre renombramos la componente mas pequeña, el tiempo amortizado para la operación de elmininar 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 constrola 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 vertices 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 mas 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 cualqueir vérice 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 estan 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 sólo para este propósito. Claramente, las aristas artificiales están utilizadas sólo 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 retoceso qué conectan este al nivel i-1 ( hay al menos una de estas aristas, la cual puede ser artificial), aristas locales que coenctan este con otras aristas en el nivel i( hay cero o más de estas aristas), o atistas de adelanto que conectan este al nivel i+1 (hay cero o más de esats 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 eliminacion 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 eliminadode 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'a 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 sólo el vértice v.

Mientras Q no está vacía:

1. w := dequeue(Q)
2. Saca w de su nivel (j), y ponerlo en nivel próximo (j+1).
3. Actualizar los vecinos:
   • Para cada arista w-x en local(w), removerla de local(x) e insertarla en adelante(x).
   • retroceso(w) := local(w)
4. 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
5. Si el nuevo retroceso(w) es vacío, encola w otra vez en Q.

Si la eliminacón de aristas no rompe cualquier componente y estamos en l caso 2.2, entonces en algun momento el procedimiento parará. En este caso es fácil de ver que la estructura BFS es mantenida correctamente. Si su eliminacó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 teniamos antes de la eliminacó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.​

Siempre que una arista  es procesada en el procedimiento, uno de su extremosdisminuye un nivel. Dado que el vértice de nivel mas bajo es  |V|-1, el coste por arista es acotado por 2|V|. P${\displaystyle }$or ello el tiempo amortizado para la operación de eliminacion  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 sólo 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 qué 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 insercción son implementadas utilizando las operaciones correspondientes en los árboles del ETque 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 diminuir 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 insercción utilizan sólo el bosque más grande FL. Los sobgrafos mas pequeños son consultados sólo durante la operacó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 eliminacó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 sólo 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 abaracadores estan 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 puedenser 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 un estructura de datos que, sin mantener el grafo entero en memoria, puede encontrar desprisa una arista en el cutset, si tal arista existe.​

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 estan 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 mas a la izquierda los lg(n) bits mas a la derecha.
• La tercera opción es que xor(T) es un número distinto de cero el cuál no representa una arista. Esto sólo 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.​

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 qué cutset(T) contiene una sola arista; entonces retornamos la arista y finalizamos.
• El caso malo es que finalmente encontramos un nivel en qué cutset(T) contiene ninguna arista; entonces informamos "fracaso", ya que sabemos que hay aristasen 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 uno de ellos tiene éxito. La probabilidad 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 uuna 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).

Ve también

• Problema dinámico (algoritmos)
• Refinamiento de partición

Referencias

• Ve también: Thorup, M. (2000). . ISBN 1581131844. doi:10.1145/335305.335345.  Proceedings Del treinta-segundo anual ACM simposio encima Teoría de informática - STOC '00. p. 343. doi:10.1145/335305.335345.   

[[Categoría:Algoritmos de grafos]]