Componenti Fortemente Connesse¶

Per la rimanente parte di questo capitolo, ci focalizzeremo su grafi di grande dimensione. Questi grafi sono per esempio i grafi prodotti dalle connessioni tra le pagine web in internet, dove gli archi corrispondono ai link tra di esse.

Questi grafi sono di grandi dimensioni. Alcuni grafi del web con alcune loro caratteristiche sono forniti per esempio all’indirizzo: http://law.di.unimi.it/datasets.php

I motori di ricerca come Google o Bing usano il fatto che le pagine sul web formano un grande grafo diretto. Per trasformare il World Wide Web in un grafo, trattiamo ogni pagina come un vertice, e gli hyperlink sulla pagina come archi che connettono un vertice all’altro. Figura 30 mostra una piccola parte del grafo prodotto seguendo i link da una pagina all’altra, cominciando dalla home page del Luther College’s Computer Science, detto seed. Questo grafo potrebbe essere enorme, ma è stato limitato ai siti internet che non sono più distanti di 10 link dal seed.

Figura 30: Il grafo prodotto dai link a partire dalla home page del Luther Computer Science

Se studiamo il grafo in Figura 30, possiamo fare alcune osservazioni. Possiamo osservare che molte delle altre pagine web si riferiscono allo stesso sito. Ci sono poi altri link a altri college in Iowa. Terzo, ci sono link a scuole di arte. Possiamo concludere che c’è una struttura sottostante che raggruppa insieme le pagine web che sono simili in gruppi detti cluster.

Un algoritmo che permette di mettere insieme vertici in cluster altamente connessi è chiamato l’algoritmo per le componenti fortemente connesse (SCC). Definiamo formalmente una componente fortemente connessa, \(C\), di un grafo \(G\), come il più grande sottoinsieme di vertici \(C \subset V\) tale che per ogni coppia di vertici \(v, w \in C\) abbiamo un cammino da \(v\) a \(w\) e un cammino da \(w\) a \(v\). Figura 27 mostra un grafo semplice con tre SCC.

Figura 31: Un grafo diretto con tre componenti fortemente connesse

Una volta che le componenti fortemente connesse sono state identificate, possiamo mostrare una vista semplificata del grafo combinando tutti i vertici in una componente in un singolo nodo più grande. La versione semplificata del grafo in Figura 31 è mostrata in Figura 32.

Figura 32: Il grafo ridotto

Ancora una volta vedremo che possiamo creare un algoritmo molto potente e efficiente usando la DFS. Prima di presentare l’algoritmo, introduciamo un’altra definizione. La trasposizione di un grafo \(G\) è definito come il grafo \(G^T\) dove tutti gli archi sono stati invertiti. Ovvero, se c’è un arco diretto da un nodo A al nodo B nel grafo originale allora \(G^T\) contiene l’arco dal nodo B al nodo A. Figura 33 e Figura 34 mostrano un grafo semplice e la sua trasposizione.

Figura 33: Un grafo \(G\)

Figura 34: La sua trasposizione \(G^T\)

Osserviamo le figure ancora. Notiamo che il grafo in Figura 33 ha due SCC. Osservando Figura 34, notiamo che esattamente le stesse due SCC.

Descriviamo adesso l’algoritmo per calcolare le SCC di un grafo.

1. Chiama dfs per il grafo \(G\) per calcolare il tempi di fine di ogni vertice.
2. Calcola \(G^T\).
3. Chiama dfs per il grafo \(G^T\) ma nel ciclo principale della DFS esplora ogni vertice in ordine decrescente rispetto al tempo di fine.
4. Ogni albero nella foresta calcolato allo step 3 è una SCC. Fai output degli id dei vertici per ogni vertice in ogni albero della foresta per identificare le componenti.

Tracciamo i passi descritti sopra sul grafo in Figura 31. Figura 35 mostra il tempo di scoperta e di fine calcolato per il grafo originale dall’algoritmo di DFS. Figura 36 mostra il tempo di scoperta e di fine calcolato dalla DFS nel grafo trasposto.

Figura 35: Tempi di fine per il grafo originale \(G\)

Figura 36: Tempi di fine per il grafo trasposto \(G^T\)

La Figura 37 mostra la foresta composta dai tre alberi prodotti dal passo 3 dell’algoritmo. Non abbiamo mostrato qui il codice Python e lo lasciamo come esercizio.

Figura 37: Componenti fortemente connesse