Usuario:Ernest930620/Dynamic connectivity (1)

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 ( α ( n ) ) {\displaystyle O(\alfa (${\displaystyle }$))} , 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 ( ${\displaystyle }$ ${\displaystyle }$ ( n ) ) {\displaystyle O(\registro(n))} .${\displaystyle }$

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. P${\displaystyle }$or ello el tiempo amortizado para ${\displaystyle }$ eliminar es otra vez O ( ${\displaystyle }$ ${\displaystyle }$ ( n ) ) {\displaystyle O(\registro(n))} .${\displaystyle }$

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 backward(v) no es vacío, entonces los componentes no han cambiado: hay otros bordes qué conectar v atrás. Proceso B para (y procesar Un está parado también).

Caso 2.2: Si el nuevo backward(v) es vacío, entonces v es ya no conectado para nivelar i-1, y así que su distancia de la raíz es ya no i; tenga que ser al menos i+1. Además, puede haber otros vértices, conectados a v, cuya distancia de los aumentos de raíz a raíz del deletion. Para calcular el actualizó distancias, utilizamos un queue Q, el cual inicialmente contiene sólo el vértice v.

Acíclico graphs (bosques)

[[Categoría:Algoritmos de grafos]]