7.18. Componentes fuertemente conectados¶
En lo restante este capítulo nos centraremos en algunos grafos extremadamente grandes. Los grafos que usaremos para estudiar algunos algoritmos adicionales son los grafos producidos por las conexiones entre servidores en Internet y los enlaces entre páginas web. Comenzaremos con las páginas web.
Los motores de búsqueda como Google y Bing explotan el hecho de que las páginas en la web forman un grafo dirigido muy grande. Para transformar la World Wide Web en un grafo, trataremos una página como un vértice y los hipervínculos de la página como aristas que conectan un vértice con otro. La Figura 30 muestra una pequeña parte del grafo que se produce al seguir los enlaces de una página a la siguiente, comenzando en la página principal de Ciencias de la Computación del Luther College. Por supuesto, este grafo podría ser enorme, por lo que lo hemos limitado a sitios web que no están a más de 10 enlaces de la página principal.
Figura 30: El grafo producido por los enlaces de la página principal de Ciencias de la Computación del Luther College¶
Figura 30: El grafo producido por los enlaces de la página principal de Ciencias de la Computación del Luther College
Usted podría hacer algunas observaciones interesantes si estudia el grafo de la Figura 30. En primer lugar, note que muchos de los otros sitios web en el grafo son otros sitios web del Luther College. En segundo lugar, usted podrá notar que hay varios enlaces a otras universidades en Iowa. En tercer lugar, notará que hay varios enlaces a otras universidades de artes liberales. Usted puede concluir de esto que hay alguna estructura subyacente a la web que agrupa sitios web que son similares en cierto nivel.
Un algoritmo de grafos que puede ayudar a encontrar grupos de vértices altamente interconectados en un grafo se llama el algoritmo de componentes fuertemente conectados (CFC). Definimos formalmente un componente fuertemente conectado, \(C\), de un grafo \(G\), como el mayor subconjunto de vértices \(C \subset V\) tal que para cada pareja de vértices \(v, w \in C\) tenemos una ruta desde \(v\) hasta \(w\) y una ruta desde \(w\) hasta \(v\). La Figura 31 muestra un grafo sencillo con tres componentes fuertemente conectados. Los componentes fuertemente conectados se identifican con áreas de sombreados diferentes.
Figura 31: Un grafo dirigido con tres componentes fuertemente conectados¶
Figura 31: Un grafo dirigido con tres componentes fuertemente conectados
Figura 32: El grafo reducido¶
Figura 32: El grafo reducido
Una vez más veremos que podemos crear un algoritmo muy potente y eficiente haciendo uso de una búsqueda en profundidad. Debemos introducir otra definición antes de enfrentarnos al algoritmo principal de CFC. La transposición de un grafo \(G\) se define como el grafo \(G^T\) donde se han invertido todos los aristas del grafo. Es decir, si hay una arista dirigida desde el nodo A hasta el nodo B en el grafo original, entonces \(G^T\) contendrá una arista desde el nodo B hasta el nodo A. La Figura 33 y la Figura 34 muestran un grafo sencillo y su transposición.
Figura 33: Un grafo \(G\)¶
Figura 33: Un grafo \(G\)
Figura 34: Su transpuesto \(G^T\)¶
Figura 34: Su transpuesto \(G^T\)
Mira las figuras otra vez. Note que el grafo de la Figura 33 tiene dos componentes fuertemente conectados. Ahora mire la Figura 34. Observe que tiene los mismos dos componentes fuertemente conectados.
Ahora podemos describir el algoritmo para calcular los componentes fuertemente conectados de un grafo.
Llamar a
beppara el grafo \(G\) con el fin de calcular los tiempos de finalización de cada vértice.Calcular \(G^T\).
Llamar a
beppara el grafo \(G^T\) pero, en el ciclo principal de BEP, explorar cada vértice en orden decreciente de tiempo de finalización.Cada árbol en el bosque, calculado en el paso 3, es un componente fuertemente conectado. Imprimir los identificadores (ids) de vértice para cada vértice en cada árbol del bosque con el fin de identificar el componente.
Vamos a hacer un seguimiento del funcionamiento de los pasos que acabamos de describir aplicados al grafo de ejemplo mostrado en la Figura 31. La Figura 35 muestra los tiempos de inicio y finalización calculados por el algoritmo BEP para el grafo original. La Figura 36 muestra los tiempos de inicio y finalización calculados mediante la ejecución de BEP para el grafo transpuesto.
Figura 35: Tiempos de finalización para el grafo original \(G\)¶
Figura 35: Tiempos de finalización para el grafo original \(G\)
Figura 36: Tiempos de finalización para \(G^T\)¶
Figura 36: Tiempos de finalización para \(G^T\)
Finalmente, la Figura 37 muestra el bosque de tres árboles producido en el paso 3 del algoritmo de componentes fuertemente conectados. Usted verá que no le proporcionamos el código en Python para el algoritmo de CFC, dejamos la escritura de este programa como un ejercicio.
Figura 37: Componentes fuertemente conectados¶
Figura 37: Componentes fuertemente conectados