componenti fortemente connesse. una componente fortemente connessa (cfc) di un grafo orientato...
TRANSCRIPT
![Page 1: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/1.jpg)
Componentifortemente connesse
![Page 2: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/2.jpg)
Componenti fortemente connesse
Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che per ogni coppia di vertici u e v in U si ha che ciascuno dei due vertici è raggiungibile dall’altro.
![Page 3: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/3.jpg)
Componenti fortemente connesse
![Page 4: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/4.jpg)
Componenti fortemente connesse
![Page 5: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/5.jpg)
Grafo trasposto
Il grafo GT=(V,ET) è il trasposto di G=(V,E) se ET = {(u,v): (v,u)E} (rovescia il senso di percorrenza degli archi di G).
G e GT hanno le stesse componenti fortemente connesse.
![Page 6: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/6.jpg)
Componenti fortemente connesse
Strongly-Connected-Components(G)1.chiama DFS(G) per calcolare f[u] per ogni vertice u2.calcola GT
3.chiama DFS(GT), ma nel ciclo principale di DFS considera i vertici in ordine decrescente di f[u]
4.return i vertici di ogni albero nella foresta DFS prodotta al passo 3 come una diversa componente fortemente connessa
L’algoritmo seguente trova in tempo lineare (O(V+E)) le componenti connesse di un grafo orientato G=(V,E).
![Page 7: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/7.jpg)
Componenti fortemente connesse
13/14
3/4
1/1011/16
2/712/15
8/9
5/6
Grafo G iniziale
![Page 8: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/8.jpg)
Componenti fortemente connesse
13/14
3/4
1/1011/16
2/712/15
8/9
5/6
Grafo GT
![Page 9: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/9.jpg)
Componenti fortemente connesse
13/14
3/4
1/1011/16
2/712/15
8/9
5/6
![Page 10: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/10.jpg)
Componenti fortemente connesse
13/14
3/4
1/1011/16
2/712/15
8/9
5/6
![Page 11: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/11.jpg)
Componenti fortemente connesse
LemmaSe due vertici sono nella stessa CFC, allora nessun cammino fra loro esce da questa CFC.
TeoremaIn una qualunque visita in profondità, tutti i vertici in una stessa CFC sono posti nello stesso albero DFS.
![Page 12: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/12.jpg)
Avi
Un avo (u) di un vertice u è il vertice (unico) w raggiungibile da u che massimizza f[w](w è l’ultimo nodo raggiungibile da u nell’ordinamento della DFS).
TeoremaIn un grafo orientato G = (V,E) l’avo (u) di un qualunque vertice uV in una qualunque visita in profondità di G è un antenato di u.
![Page 13: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/13.jpg)
Componenti fortemente connesse
CorollarioIn ogni visita in profondità di un grafo orientato G = (V,E), per ogni vertice uV i vertici u e (u) appartengono alla stessa CFC.
TeoremaIn un grafo orientato G = (V,E), due vertici u,vV appartengono alla stessa CFC se e solo se essi hanno lo stesso avo in una visita in profondità di G.
![Page 14: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/14.jpg)
CorrettezzaTeoremaStrongly-Connected-Components(G) calcola correttamente le CFC di un grafo orientato G.
Dim.Per induzione. Tesi: se tutti gli alberi prodotti prima dell’n-esimo nella DFS sono CFC, allora lo è anche l’n-esimo.
Banalmente vero per n=0.
Per il caso induttivo, cont...
![Page 15: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/15.jpg)
Considera un albero DFS, T con radice r prodotto dalla ricerca per profondità su GT, sia C(r) l’insieme dei vertici con avo r.
Tesi: un vertice u è presente in T, sse u è in C(r).
Chiaramente, ogni vertice in C(r) è anche in T.
Se f[(w)]>f[r], allora w non può essere in C(r):– Quando r viene selezionato, w è già stato inserito
nell’albero con radice (w).
Se f[(w)]<f[r], allora w non può essere in C(r):– Se w fosse in C( r), allora r sarebbe raggiungibile da w.
Quindi r f[r]<f[(w)]
![Page 16: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/16.jpg)
Problema: dato un grafo orientato …
![Page 17: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/17.jpg)
… trovare le sue CFC
![Page 18: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/18.jpg)
Inizio
Prima DFS
![Page 19: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/19.jpg)
Inizio
![Page 20: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/20.jpg)
Inizio
![Page 21: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/21.jpg)
![Page 22: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/22.jpg)
4
3
1
2
7
5
8
6
Identificazione dei tempi di fine visita
![Page 23: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/23.jpg)
4
3
1
2
7
5
8
6
Transposizione del grafo
![Page 24: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/24.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 25: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/25.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 26: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/26.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 27: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/27.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 28: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/28.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 29: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/29.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 30: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/30.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 31: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/31.jpg)
4
3
1
2
7
5
8
6
Seconda DFS
![Page 32: Componenti fortemente connesse. Una componente fortemente connessa (CFC) di un grafo orientato G=(V,E) è un insieme massimale di vertici U V tale che](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb66497959361e8d2714/html5/thumbnails/32.jpg)
4
3
1
2
7
5
8
6
Seconda DFS