Dato un grafo diretto G=(V,E), una componente fortemente connessa (SCC, Strongly Connected Component) è un insieme massimale di vertici U sottoinsieme di V tale che per ogni coppia di vertici u e v in U, u è raggiungibile da v e viceversa.
Dato un grafo, l’operazione di decomposizione nelle sue componenti fortemente connesse ha molte applicazioni pratiche.
Per esempio:
L’algoritmo che proponiamo per la decomposizione di un grafo nelle sue componenti fortemente connesse usa due visite in profondità, una sul grafo G e l’altra sul grafo trasposto G’.
Algoritmo per SCC:
Per calcolare f[v], si noti che nella vista in profondità, a ciascun vertice si possono associare due tempi: il primo corrisponde a quando il nodo è scoperto, il secondo corrisponde a quando la ricerca finisce di esaminare i suoi adiacenti.
Di seguito riportiamo i 4 alberi risultanti che formano i quattro SCC del grafo dato.
Un albero ricoprente di un grafo G=(V,E) è un albero T=(V’,E’) tale che V’ =V e E’ è un sottoinsieme di E.
Si ricorda che un albero è un grafo (non orientato) connesso e senza cicli. Ricordiamo anche che un ciclo in un grafo è un cammino in cui il nodo di partenza e di destinazione coincidono e che non passa due volte per nessun nodo intermedio.
Il problema del Minimo Albero Ricoprente (in breve, MST, Minimum Spanning Tree) è definito come segue:
L’importanza di tale problema è enorme. A titolo di esempio, si supponga di dover realizzare l’impianto di distribuzione dell’energia elettrica di una zona, nella quale esistono un certo numero di abitazioni che devono essere servite. Si supponga che di ogni abitazione si conosca la posizione, nonché la distanza da tutte le altre. L’albero di copertura minimo rappresenta la soluzione che consente la minimizzazione della lunghezza dei collegamenti da realizzare.
Nota: L’albero di copertura minimo per un grafo in generale non è unico.
Gli algoritmi per il calcolo di un albero di copertura minimo che vedremo, si basano su un approccio chiamato greedy.
Gli algoritmi greedy rappresentano una particolare categoria di algoritmi di ricerca o ottimizzazione.
In molti problemi ad ogni passo l’algoritmo deve fare una scelta: seguendo la strategia greedy (ingordo), l’algoritmo fa la scelta più conveniente in quel momento.
Esempio: Supponiamo di avere un sacchetto di monete di euro e di voler comporre una precisa somma di denaro x, utilizzando il minor numero di monete. La soluzione consiste nel prendere dal sacchetto sempre la moneta più grande tale che sommata alle monete scelte in precedenza il totale non sia superiore a x.
In molti casi (ma non sempre), la tecnica greedy fornisce una soluzione globalmente ottima al problema.
L’idea generale per calcolare un MST T su un grafo G è la seguente:
T=NULL;
while T non forma un albero di copertura;
do trova un arco (u,v) che sia sicuro per T;
T=T unito a {(u,v)};
return T
Si definisce sicuro un arco che aggiunto ad un sottoinsieme di un albero di copertura minimo produce ancora un sottoinsieme di un albero di copertura minimo.
In seguito vedremo due tecniche per calcolare un arco sicuro. Entrambe queste tecniche utilizzano il concetto di taglio di un grafo.
Dato un grafo non orientato G=(V,E), un taglio è una partizione di V in due sottoinsiemi.
Un arco attraversa il taglio se uno dei suoi estremi è in una partizione, e l’altro nell’altra.
Un taglio rispetta un insieme A di archi se nessun arco di A attraversa il taglio.
Un arco si dice leggero se ha peso minimo tra gli archi che attraversano il taglio.
Esempio:
Siano gli archi in rosso un sottoinsieme A di E. Il taglio rispetta chiaramente A.
Se invece A è l’insieme degli archi adiacenti ai nodi d ed e, allora l’arco (d,c) è leggero per il taglio dato.
Teorema:
In seguito analizziamo in dettaglio due algoritmi che calcolano un BST di un grafo formato da tutti archi sicuri calcolati utilizzando una tecnica greedy:
Esempio:
Si consideri il seguente grafo. Inizialmente ogni insieme costituisce un insieme a se.
La complessità dell’algoritmo di Kruskal dipende fondamentalmente dall’ordinamento degli archi pesati che prende tempo O(E log E).
L’algoritmo di Prim parte da un nodo radice r ed espande ad ogni passo l’albero di copertura minimo A, sino a che questo non copre tutti i vertici.
Ad ogni passo viene aggiunto all’albero un arco leggero che collega un vertice in A ad un vertice in V-A.
Per la scelta dell’arco leggero si usa una coda di priorità.
Ad ogni istante la coda di priorità contiene tutti i vertici non appartenenti all’albero A.
La posizione di ciascun vertice v nella coda dipende dal valore di un campo chiave key[v], corrispondente al minimo tra i pesi degli archi che collegano v ad un qualunque vertice in A.
Se v non è collegato a nessun vertice in A, allora key[v]=∞.
Studi approfonditi dimostrano che la complessità asintotica dell’algoritmo di Prin è migliore dell’algoritmo di Kruskal.
1. Introduzione al Corso - Il Linguaggio C (I parte)
2. Linguaggio C – Seconda Parte
3. Ordinamento, Ricorsione e Code di Priorità
4. Esercitazione su Ricorsione e Code di Priorità
5. Stack e Code
6. Esercitazione di Laboratorio su Stack e Code
7. Implementazioni di Liste puntate
8. Esercitazione di laboratorio su Liste Puntate Semplici
9. Implementazioni di Liste Doppiamente Puntate e Circolari
10. Esercitazione di laboratorio su Liste Doppiamente puntate
12. Esercitazione di laboratorio su Alberi Binari di Ricerca
13. Alberi Binari di Ricerca. Cancellazione di un nodo
14. Esercizio di Laboratorio. Gioco su alberi
15. Grafi: Implementazione ed operazioni di base
16. Esercitazione di laboratorio: Implementazione operazioni di bas...
17. Grafi: Inserimento e Cancellazione di un nodo. Visite in ampiez...
18. Esercitazione di laboratorio: Problema del venditore Prima part...
19. Componenti fortemente connesse e alberi minimi di copertura
20. Esercitazione di laboratorio: Problema del venditore Seconda pa...