10.8. Puntos de articulación (vértices de corte).

Teniendo una gráfica conexa, llamamos punto de articulación a todos los vértices que siendo borrado ocasionarían que la gráfica dejara de ser conexa (podemos decir que es el equivalente en vértice a los puentes). Cuando una gráfica no contiene puntos de articulación se dice que es “dos conexa”.

Para encontrar todos los puntos de articulación de una gráfica conexa, podemos utilizar una búsqueda en profundidad y realizar algunas operaciones adicionales. Al realizar la búsqueda en profundidad de la gráfica, nos van a sobrar aristas (que son las que formarían ciclos en el árbol de búsqueda). A estas aristas sobrantes las llamaremos aristas de conexión.

En el caso particular de un árbol, sabemos que un vértice es punto de articulación si al tomarlo como raíz tiene más de un hijo (ya que al quitarlo, cada hijo se convertiría en raíz de un árbol). En general, un vértice es un punto de articulación si, al realizar la búsqueda en profundidad, no podemos encontrar para cada uno de sus hijos un vértice descendiente (nivel menor) que comparta una arista de conexión con un vértice ascendente (nivel mayor, incluyendo al padre), con lo que habría un camino alterno para llegar. Esto cumple para cualquier vértice, excepto la raíz de la búsqueda. Para saber si la raíz es punto de articulación, sólo debemos contar sus hijos de manera análoga a un árbol, pero recordando no incluir los que están unidos por una arista de conexión. Por ejemplo:

Figura 10.2: Gráfica con puntos de articulación en 1 y 2, y arista de conexión entre 1 y 4

En esta gráfica, la raíz (1) es punto de articulación porque tiene dos hijos (2 y 7). Para el vértice 2, aunque su hijo 3 no cumple la condición porque 4 tiene una arista de conexión con 1, como 5 y 6 cumplen entonces también es punto de articulación. Sólo los vértices 1 y 2 son puntos de articulación.


Problema ejemplo


Redes

Problema
La Compañía de Líneas Telefónicas (CLT) está por instalar un cableado telefónico nuevo. Están conectando varios sitios, los cuales están numerados de 1 a n. Dos sitios nunca comparten un mismo número. Las líneas son bidireccionales, y cada línea une a dos sitios. En cada sitio, al final de la línea hay un solo teléfono. Siempre es posible marcar de un teléfono a otro, aunque no siempre a través de una conexión directa (puede pasar por varios sitios). En ocasiones, a un sitio le falla el suministro eléctrico y ya no puede conectar. Los directivos de CLT se han dado cuenta que puede pasar que no solo ese sitio quede inalcanzable, sino que puede causar que otros sitios también los sean. En estos casos, decimos que el sitio (donde ocurrió el fallo) es crítico. Ahora los directivos quieren contar con un programa que encuentre la cantidad de sitios críticos. Ayúdalos.

Entrada
La entrada consiste en varios bloques de líneas. Cada bloque describe una red. En la primera línea de cada bloque está la cantidad de lugares n < 100. Cada una de las siguientes líneas, a lo más n, contiene el número de un sitio seguido por los números de los sitios a los que tiene conexión directa. Estas líneas, que no pasan de n, describen a la red; esto es, todas las conexiones directas entre dos sitios dentro de la red están descritas en estás líneas. Todos los números en cada línea están separados por un espacio. Cada bloque termina con una línea que tiene sólo un 0. El último bloque sólo tiene una línea con n = 0.

Salida
La salida debe contener para cada bloque en la entrada, excepto el último, una línea con la cantidad de sitios críticos.

Solución: Según la descripción del problema, los lugares críticos son los que desconectan la gráfica, por lo que son puntos de articulación. Entonces, lo que buscamos son todos los puntos de articulación en la gráfica.


Código


Empezamos declarando las variables que vamos a utilizar. Al igual que en problemas anteriores, el arreglo m va a ser la matriz de adyacencia y el arreglo vis lo utilizamos para saber si un vértice ya lo utilizamos. Los enteros a y b los vamos a usar para leer los vértices de las aristas, n para saber cuantos lugares hay, h para saber cuantos hijos tiene la raíz, c para numerar los vértices de acuerdo al orden en que los recorremos y t para contar la cantidad de puntos de articulación.

  La función recorre (líneas 6 a 26) realiza una búsqueda en profundidad modificada. Como parámetro tenemos v, que es el vértice que estamos visitando, y la función devuelve el valor mínimo de los vértices con los que está conectado. El booleano b nos sirve para saber si todos los hijos del vértice tienen una conexión arriba, el entero i los usamos para los ciclos, d como variable temporal y min para guardar el vértice mínimo con el que está conectado. Como ya habíamos visto, el arreglo vis los usaremos para saber si un vértice ya lo utilizamos, pero le agregaremos que si ya lo visitamos guarde el valor de en que momento lo visitamos.

Empezamos inicializando a b como verdadero (línea 10), incrementando la numeración del vértice en el que vamos (línea 11), y asignando este valor a vis (para saber cuando lo visitamos) y a min (porque la conexión más alta que tiene en este momento es consigo mismo). Después recorremos todos los vértices, y si tiene conexión con el actual (línea 15), revisamos si no lo hemos visitado (línea 16). En caso de que lo hayamos hecho, vemos si la conexión con este vértice es menor a la que teníamos (línea 23); en caso contrario, visitamos el vértice y al regresar examinamos si alguno de los hijos tiene una conexión con un vértice menor al que tenemos (línea 19), si algunos de los hijos no tiene conexión con un vértice mayor al actual lo marcamos en b (línea 20), y si el vértice actual es la raíz, incrementamos la cantidad de hijos (línea 21). Después de visitar todos los vértices, si alguno de los hijos no tiene conexión con alguno menor, entonces es un punto de articulación a menos de que estemos en la raíz (línea 24). Terminamos devolviendo el valor de min.

Los puntos de articulación los obtenemos en la función que se encuentra entre las líneas 28 y 42. Empezamos inicializando la cantidad de estos puntos a cero (línea 31), y a los vértices como no visitados (línea 32). Recorremos todos los vértices, y en caso de que no hayamos visitado alguno, inicializamos tanto la cantidad de hijos de la raíz como el contador de vértices a cero (líneas 36 y 37), y realizamos la búsqueda en profundidad. Después de realizar la búsqueda, si la raíz tiene más de un hijo incrementamos la cantidad de puntos (línea 39). Terminamos devolviendo el total (línea 41). El ciclo de la línea 33 nos ayuda a encontrar los puntos de articulación en todas las componentes de la gráfica, por lo que si la gráfica es conexa no lo necesitamos.

La parte principal del código la tenemos entre las líneas 44 y 65. Al comenzar leemos la cantidad de lugares (línea 45). Mientras sea distinto de cero, leemos la gráfica y encontramos sus puntos de articulación.


Caso ejemplo

Entrada: 5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0
Desarrollo:  v  min   b         vis[]
 1:  1  TRUE;   1, 0, 0, 0, 0
 5:  1  TRUE;   1, 0, 0, 0, 2 ←
 2:  2  FALSE;  1, 3, 0, 0, 2
 3:  2  FALSE;  1, 3, 4, 0, 2
 4:  2  FALSE;  1, 3, 4, 5, 2

 v  min   b         vis[]
 1:  1  TRUE;   1, 0, 0, 0, 0, 0
 2:  1  TRUE;   1, 2, 0, 0, 0, 0 ←
 3:  2  FALSE;  1, 2, 3, 0, 0, 0
 5:  2  TRUE;   1, 2, 3, 0, 4, 0 ←
 4:  4  FALSE;  1, 2, 3, 5, 4, 0
 6:  4  FALSE;  1, 2, 3, 5, 4, 6
Salida: 1
2


Código en C



Tiempo de ejecución

Lenguaje Fecha Tiempos [s] Memoria [Kb]
Ejecución Mejor Mediana Peor
Pascal 31-May-2006 0.029 0.004 0.650 79.110 Minimum
C 26-Jun-2006 0.035 Minimum


Otros problemas

Valladolid:





© Pier Paolo Guillen Hernandez
World of πer