Download Vamos a estudiar algoritmos y problemas relacionados con la

Introducción:
Este trabajo se dedica a estudiar algoritmos y problemas relacionados con la conectividad en
grafos. Nos vamos a interesar en saber si hay más de un camino para ir desde un vértice de un grafo a
otro. Por eso vamos a introducir el concepto de bi-conexo.
Definición:
Un grafo es bi-conexo si y solo si hay por lo menos dos caminos diferentes conectando cada par
de vértices. Es decir que si se remueve un vértice y todas las aristas que llegan a él, el grafo sigue siendo
conexo.
Si para alguna aplicación es importante que un grafo sea conexo, también puede ser importante
que luego de una eliminación, éste siga siendo conexo. Este problema se resuelve por búsqueda de
primero en profundidad.
Una versión particular de problemas de conectividad que aparece frecuentemente es cuando en
una situación dinámica se van agregando aristas al grafo una por una. Mientras se va preguntando si dos
vértices en particular pertenecen al mismo componente conexo. Es un problema bien estudiado y vamos a
presentar dos algoritmos “Clásicos” relacionados con esto. El problema es a veces llamado “Union find”
(encontrar uniones).
Bi-conectividad
A veces es útil diseñar más de una ruta entre dos puntos en un grafo, para poder manejar posibles
fallas en los puntos de conexión (vértices). Por ejemplo, se tiene un mapa de caminos y una carga a
transportar que debe llegar si o si. Justo en ese momento a los piqueteros se les ocurre cortar una ruta.
Sería muy útil si tengo otro camino para poder llegar a mi destino. Las principales líneas de comunicación
en un circuito integrado son por lo general bi-conexas, para que el resto del circuito pueda seguir
funcionando si un componente falla. Otra aplicación (no muy realista pero puede aclarar el concepto) es
imaginarse una guerra donde necesitamos hacer que el enemigo tenga que destruir al menos dos
estaciones para cortar las líneas de tren.
Un punto de articulación en un grafo conexo es un vértice que, si es eliminado, hace que se
quiebre el grafo en dos o más partes. Un grafo sin puntos de articulación se dice que es bi-conexo. En un
grafo bi-conexo dos caminos distintos conectan cada par de vértices.
La figura muestra un grafo conexo pero
no bi-conexo. Los puntos de articulación de este
grafo son: A (porque conecta a B al resto del
grafo), H (porque conecta a I al resto del grafo),
J (porque conecta a K al resto del grafo) y G
(porque el grafo se partiría en tres si se borrara
G). Hay seis componentes bi-conexas: {A C G D
E F}; {G J L M}; y los nodos individuales B; H;
I y K.
Determinar los puntos de articulación
termina siendo una simple extensión de
búsqueda primero en profundidad. Para entender
esto vamos a ver el árbol de búsqueda de
primero en profundidad de este grafo, que vemos en la próxima figura. Eliminando el nodo E no se
1
desconecta el grafo, porque ambos G y D tienen líneas
curvas que apuntan debajo de E, dándoles caminos
alternativos para llegar a F (el padre de E en el árbol). Por
lo contrario si se elimina G, el grafo se desconecta porque
no hay caminos alternativos desde L o H hasta E (padre de
G).
Un vértice x no es un punto de articulación si todo
hijo y tiene algún nodo más abajo en el árbol conectado
(por una línea curva) a un nodo más alto en el árbol que x,
proveyendo así una conexión alternativa entre x y y. Este
testeo no funciona muy bien para la raíz, ya que no hay
ningún nodo más alto en el árbol. La raíz es un punto de
articulación si tiene dos o más hijos, ya que el único camino conectando hijos de la raíz pasa por la raíz.
Estas pruebas se incorporan fácilmente en la búsqueda primero en profundidad, cambiando el
procedimiento de visita a los nodos por una función que devuelva el punto más alto en el árbol visto
durante la búsqueda:
int visit(int k)
//búsqueda primero en profundidad para buscar
{
//puntos de articulación
struct node *t;
int m, min;
val[k] = ++id;
min = id;
for (t=adj[k]; t!=z; t=t->next)
if(val[t->v]==unseen)
{
m = visit(t->v);
if(m<min)
min = m;
if(m>=val[k])
cout << name[k];
}
else if (val[t->v] < min)
min = val[t->v];
return min;
}
Este procedimiento determina recursivamente el punto alcanzable más alto del árbol (por una línea
curva) desde cualquier descendente del vértice k y usa esta información para determinar si k es un punto
de articulación. Normalmente este cálculo solo involucra probar si el mínimo valor alcanzable desde un
hijo esta más alto en el árbol o no. Sin embargo necesitamos una prueba auxiliar para determinar si k es la
raíz del árbol de búsqueda de primero en profundidad (o, equivalentemente, si esta es una primer llamada
a visit para el componente conexo conteniendo a k), ya que usamos el mismo programa recursivo para
ambos casos. Esta prueba es realizada fuera de la visita recursiva y por eso no aparece en este código.
Propiedad: Los componentes bi-conexos de un grafo pueden hallarse en tiempo real.
Aunque el programa recién visto, solo imprime los puntos de articulación, se puede extender
fácilmente para que haga un procesamiento extra en los puntos de articulación y en los componentes biconexos. Como es un procedimiento de búsqueda primero en profundidad, el tiempo de proceso es
equivalente a V+A (un programa similar basado en la matriz de adyacencia correría en O(V2) pasos).
Además de las utilidades antes mencionadas, donde la bi-conectividad es usada para lograr
confiabilidad, puede ser útil en la descomposición de grandes grafos en piezas manejables. Es obvio que
2
un grafo muy grande puede ser procesado de a un componente conexo a la vez para muchas aplicaciones.
Es, quizás, un poco menos obvio, pero ocasionalmente igual de útil que un grafo pueda ser procesado de a
un componente bi-conexo a la vez.
Algoritmos de búsqueda de uniones:
En algunas aplicaciones se desea saber simplemente si un vértice x esta o no conectado a otro y en
un grafo; el camino que los conecta puede no ser relevante. Los algoritmos eficientes que se han
desarrollado para solucionar estos problemas son de mucho interés porque pueden ser usados para
procesar grupos de objetos. Los grafos se corresponden a grupos de objetos en un modo natural: los
vértices representan objetos y las aristas significan “esta en el mismo grupo que”. Otra forma de llamar a
estos grupos es “Clases de Equivalencia”. Cada componente conexo corresponde a una diferente clase de
equivalencia. Agregar una arista corresponde a combinar las clases de equivalencia representadas por los
vértices a unir. La pregunta es entonces: ¿es x equivalente a y? que es lo mismo que: ¿esta x en el mismo
grupo que y? Esto se corresponde con la pregunta para grafos: ¿está x conectado con y?
Dado un grupo de aristas, se puede representar una lista de adyacencias del correspondiente grafo
y usar la búsqueda primero en profundidad para asignarle a cada vértice el índice de su componente
conexo, entonces la pregunta ¿esta x conectado con y? se puede responder con solo dos accesos a arrays y
una comparación. La ventaja de los métodos que se van a mostrar es que son dinámicos: se les puede
agregar nuevas aristas y al mismo tiempo ir haciéndoles la pregunta. El agregado de una nueva arista se
llama operación de unión (union operations) y las preguntas se conocen como operaciones de encuentro
(find operations).
El objetivo es escribir una función que pueda chequear si dos vértices x y y están en el mismo
grupo (o, en la representación del grafo, en el mismo componente conexo) y, sino, ponerlos en el mismo,
es decir, agregar una arista entre ambos. En lugar de hacer una lista de adyacencia directa u otra
representación para el grafo, se ganará eficiencia si se usa una estructura interna especialmente orientada
al soporte de las operaciones de unión y encuentro. Esta estructura interna será un bosque de árboles, uno
para cada componente conexo. Necesitamos tener la posibilidad de averiguar si dos componentes están en
el mismo árbol y además poder combinar dos árboles en uno. Resulta ser que estas dos operaciones se
pueden implementar eficientemente.
Para ilustrar como trabaja este algoritmo, vamos a ver el bosque construido por los siguientes
vértices (A-B-C-D-E-F-G-H-I-J-K-L-M) cuando se le insertan estas aristas en el siguiente orden: AG –
AB – AC – LM – JM – JL – JK – ED – FD – HI – FE – AF – GE – GC – GH – JG – LG.
Inicialmente todos los nodos están en árboles separados (cada vértice es un árbol). Luego la arista AG
crea un árbol de dos nodos con A como raíz (esta decisión es arbitraria, porque tranquilamente podríamos
haber puesto G como raíz). Las aristas AB y AC agregan B y C al árbol de la misma forma. Luego las
aristas LM, JM, JL y JK construyen un árbol conteniendo a J, K, L y M que tiene una estructura un
poco distinta (nótese que la arista JL no contribuye en nada, ya que LM y JM ponen a L y J en el mismo
componente). Las aristas ED, FD, y HI construyen dos árboles más, dejando un bosque con cuatro
árboles. Éste bosque describe un grafo con cuatro componentes conexas, o, lo que es lo mismo, las
operaciones de unión procesadas hasta el momento han terminado en cuatro grupos: {A B C G}, {J K L
M}, {D E F}, {H I}. Ahora la arista FE no contribuye a la estructura, ya que F y E están en el mismo
componente, pero la arista AF combina los dos primeros árboles; luego GE y GC no contribuyen, pero
GH y GJ hacen que se combine todo en un solo árbol.
Es necesario recalcar que, al contrario que en los árboles de búsqueda primero en profundidad, la
única relación entre estos árboles de unión y el grafo original con las aristas dadas es que dividen a los
vértices en grupos de la misma forma. Por ejemplo, no hay ninguna correspondencia entre los caminos
que conectan nodos en los árboles y los caminos que conectan nodos en el grafo.
3
4
Para representar estos árboles es apropiado usar la representación “parent-link”1 porque siempre
se viaja hacia arriba en los árboles, nunca hacia abajo. Específicamente, mantenemos un array padre que
contiene, para cada vértice, el índice de su padre (0 si es la raíz de algún árbol), como se especifica en la
próxima declaración de la clase:
class EQ
{
private:
int *dad;
public:
EQ(int size);
Int find(int x, int y, int doit);
};
El constructor reserva el espacio para el array dad y setea todos sus valores inicialmente a cero
(se omite el código). Se usa un solo procedimiento find para implementar ambos, la unión y la
búsqueda. Si el tercer argumento es 0 se hace una búsqueda, si no es 0, se hace una unión. Para
encpontrar al padre del vértice j, simplemente se hace j = dad[j], y para encontrar la raíz del árbol al
que pertenece j se repite esta operación hasta que se llega a 0. Esto nos lleva a la siguiente
implementación del procedimiento:
Int EQ::find(int x, int y, int doit)
{
int i=x, j=y;
while (dad[i] >0)
i = dad[i];
while (dad[j] > 0)
j=dad[j];
if (doit && (i!=j))
dad[j]=i;
return (i ¡= j);
}
La función find retorna 0 si los dos vértices dados están en el mismo componente. Si no lo están
y el flag doit esta seteado, son puestos en el mismo componente. El método es simple. Usar el array
dad para llegar a la raíz del árbol que contiene cada vértice, luego chequear si las raíces son las mismas.
Para mezclar el árbol con raíz j con el árbol de raíz i simplemente se setea dad[j] = i.
La siguiente figura muestra los contenidos de la estructura de datos durante éste proceso.
Asumimos que las funciones index y name están disponibles para traducir nombres de vértices a
enteros entre 1 y V. Cada entrada de la tabla es el nombre del correspondiente array de entrada dad. Por
ejemplo, antes de declarar una instancia de la clase EQ (ej: EQ eq(max)), se testearía si un vértice
llamado x esta en el mismo componente que otro llamado y (sin necesidad de poner una arista entre ellos)
con la llamada a función eq.find(index(x), index(y), 0).
Esta clase esta codificada de tal forma que puede ser usada en cualquier aplicación donde las
clases de equivalencia jueguen un papel importante, no sólo para conectividad en grafos. El único
requisito es que los elementos tengan nombres enteros que puedan ser usados como índices (de 1 a V).
1
Algoritms in C++, Robert Sedgewick – Chapter 4
5
El algoritmo descrito anteriormente
tiene un mal desempeño para su peor caso
porque los árboles formados pueden ser
degenerados. Por ejemplo, tomando en orden
las aristas AB BC CD DE EF FG GH HI
IJ… YZ se produce una larga cadena con Z
apuntando a Y, Y apuntando a X, etc. Este tipo
de estructura toma un tiempo proporcional a
V2 para construirse y tiene un tiempo
proporcional a V para una prueba promedio de
equivalencia.
Varios métodos han sido sugeridos
para lidiar con esta dificultad. Un método
natural es tratar de hacer lo correcto para
mezclar dos árboles, en lugar de hacer
arbitrariamente dad[j] = i. Cuando un
árbol con raíz en i va a ser mezclado con otro
con raíz en j, uno de los nodos debe
mantenerse como raíz y el otro (y todos sus
descendientes) deben ir un nivel más abajo en
el árbol. Para minimizar la distancia a la raíz
de la mayoría de los nodos tiene sentido elegir
como raíz el nodo con más descendientes. Esta
idea, llamada weight balancing (balanceo de
peso),
es
fácilmente
implementable
manteniendo el tamaño de cada árbol (cantidad de descendientes de la raíz) en el array dad para cada
nodo raíz, codificado como un número no positivo de tal modo que el nodo raíz pueda ser detectado
cuando se viaja hacia arriba en el árbol con find.
Idealmente se desearía que cada nodo apuntara directamente a la raíz de su árbol. Sin importar que
estrategia se use, para lograr este objetivo se necesita examinar al menos todos los nodos en uno de los
dos árboles a mezclar y esto puede ser demasiado comparado con los pocos nodos en el camino a la raíz
que find generalmente examina. Sin embargo podemos aproximarnos a este ideal haciendo que todos
los nodos que sí se examinan apunten a la raíz. Este método, conocido como path compression
(compresión de caminos), se implementa fácilmente haciendo otra pasada por cada árbol, después de que
la raíz fue encontrada, y seteando la entrada dad de cada vértice encontrado a lo largo del camino para
que apunte a la raíz.
La combinación de path compression y weight balancing nos aseguran que los algoritmos van a
correr muy rápido. La siguiente implementación muestra que el código extra necesario es un pequeño
precio a pagar para protegernos de los casos degenerados.
int EQ::find(int x, int y, int doit)
{
int t, i=x, j=y;
while (dad[i] > 0)
i=dad[i];
while (dad[j] > 0)
j=dad[j];
while (dad[x]>0)
{
t=x;
x=dad[x];
dad[t]=i;
}
6
while (dad[y]>0)
{
t=y;
y=dad[y];
dad[t]=j;
}
if (doit && (i!=j))
if (dad[j] < dad[i])
{
dad[j]+=dad[i] - 1;
dad[i]=j;
}
else
{
dad[i]+=dad[j] - 1;
dad[j]=i;
}
return (i!=j);
}
7
La figura anterior muestra los pasos que se van cumpliendo cuando este método es aplicado al
ejemplo anterior. El largo de camino promedio es de 31/13 ≈ 2.38 mientras que para el método anterior es
de 38/13 ≈ 2.92. Para las 5 primeras aristas los árboles generados son los mismos, pero después empiezan
a variar por la compensación del peso. Los árboles son tan chatos en este ejemplo que todos los vértices
involucrados en un proceso de unión estan en la raíz o justo por debajo.
La figura siguiente muestra los
contenidos del array dad mientras se
construye este bosque. Por claridad se
reemplazó cada entrada positiva i por le
i-ésima letra del abecedario (nombre del
padre), y cada entrada negativa es
complementada para dar un entero
positivo (peso del árbol).
Muchas otras técnicas fueron
desarrolladas para evitar estructuras
degeneradas.
Por
ejemplo,
path
compression tiene la desventaja que
requiere otra pasada por el árbol. Otra
técnica llamada halving (dividir a la
mitad) hace que cada nodo apunte a su
abuelo en su camino hacia el árbol. Otra
técnica distinta es splitting (separando),
es como halving pero es aplicada sólo a
todo otro nodo en el camino de
búsqueda. Cualquiera de estas pueden ser
usadas en combinación con weight
balancing o con height balancing, la cual
es similar sólo que usa la altura de los
árboles para decidir de que forma
mezclar los árboles.
Poder saber que método elegir y cuan chato va a ser el árbol requiere un análisis complicado. La
performance de depende no solo de vértices y aristas sino también de la cantidad de operaciones find y,
lo que es peor, del orden en que las operaciones union y find aparecen. Es difícil ver modelos de
grafos y patrones que puedan aparecer en la práctica, por eso los algoritmos que andan bien en los peores
casos son generalmente preferidos para union-find.
Incluso cuando se toma el peor caso, analizar algoritmos de union-find es muy complicado e
intrincado. Esto puede ser visto en la naturaleza de los resultados, que sin embargo nos dan claras
indicaciones de cómo los algoritmos se van a desempeñar en una situación práctica.
Propiedad: Si se usa weight balancing o height balancing en combinación con compresión, halving o
splitting, luego el número total de operaciones requeridas para construir una estructura usando A aristas
es casi (pero no siempre) lineal.
Precisamente el número de operaciones requeridas es proporcional a Eα(E), donde α(E) es una
función que crece tan lento que α(E)<4 al menos que E sea tan grande que tomando log(E), luego
tomando logaritmo del resultado, luego tomando logaritmo del resultado, y así repitiéndolo hasta 16 veces
sigue dando un número mayor a 1.
Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(Log(E))))))))))))))))) > 1
8
Este es un número muy grande, por lo cual se puede asumir que el tiempo promedio para ejecutar
una operación de union y find es constante. Este resultado se le atribuye a R. E. Tarjan, quien además
demostró que ningún algoritmo para este problema puede trabajar mejor que Eα(E) (esta función es
intrínseca del problema).
Aplicaciones prácticas:
Una aplicación práctica de los algoritmos de union-find es determinar si un grafo con V vértices y
A aristas es conexo en un tiempo proporcional a V (tiempo real). Esta es una ventaja sobre búsqueda
primero en profundidad en algunas situaciones: aquí no necesitamos volver a guardar las aristas. Entonces
la conectividad en un grafo con miles de vértices y millones de aristas puede ser determinada con una
rápida pasada por las aristas.
Bibliografía:

Algorithms in C++ - Robert Sedgewick – Capítulo 30
Traducido y resumido por Marcelo Indarramendi
Quejas y dudas en [email protected]
9