Grafi: Componenti Fortemente Connesse - PDF
Document Details
Uploaded by SteadyBoltzmann
Università di Torino
Ugo de’Liguoro, András Horváth
Tags
Summary
Questi appunti trattano le componenti fortemente connesse nei grafi, partendo dalla definizione e fornendo algoritmi per il calcolo. Il documento include esempi e dimostrazioni.
Full Transcript
Indice 1. Definizione 2. Algoritmo naive...
Indice 1. Definizione 2. Algoritmo naive Grafi: componenti fortemente connesse 3. Algoritmo basato su DFS Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 1/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 2/ 30 Sommario 1. Definizione di componenti fortemente connessi (cfc) Obiettivo: I due nodi u e v sono mutuamente raggiungibili se u è raggiungibile da v e v è I capire il concetto “componente fortemente connessa” raggiungibile da u I sviluppare un algoritmo per trovare le componenti fortemente connesse sulla I in un grafo G = (V , E) orientato la relazione su V × V “mutuamente base di una visita DFS raggiungibile” è una relazione di equivalenza (riflessività, simmetria, transitività) I le componenti fortemente connesse di un grafo orientato G = (V , E) sono le classi della relazione di equivalenza su V × V “mutuamente raggiungibile” I useremo la notazione u ↔ v per indicare che i vertrici u e v sono mutuamente raggiungibili e quindi fanno parte della stessa cfc Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 3/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 30 1. Definizione di componenti fortemente connessi (cfc) 2. Calcolo della cfc di un vertice I sia x un vertice di un grafo orientato G = (V , E) 1. calcola l’insieme D(x) dei vertici di G che sono raggiungibili da x 2. calcola l’insieme A(x) dei vertici di G da cui x è raggiungibile 3. calcola D(x) ∩ A(x) I 3 cfc: {A},{D, B, C},{E, F } Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 30 2. Calcolo della cfc di un vertice 2. Calcolo di tutte le cfc I la complessità è O(|V | + |E|): I sia G = (V , E) un grafo orientato 1. è sufficente una visita a partire da x marcando i vertici raggiunti (costo: I per ogni vertice x non ancora marcato, calcola la componente fortemente O(|V | + |E|)) connessa di x marcandone tutti i vertici 2. è sufficente calcolare il grafo trasposto GT di G (tutti gli archi invertiti, costo: O(|V | + |E|)) ed effettuare di nuovo una visita a partire da x marcando i vertici I costo: O(|V |2 + |V | · |E|) raggiunti (costo: O(|V | + |E|)) 3. l’intersezione può essere calcolata durante la 2. visita Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I lemma I: se x ↔ y allora nessun cammino tra essi può uscire dalla loro cfc I teorema I: in una qualunque DFS di un grafo G orientato tutti i vertici di una I dimostrazione: cfc vengono collocati nello stesso albero I sia x ↔ y I dimostrazione: I sia z tale che esiste un cammino x → z → y I sia r il primo vertice scoperto di una data cfc I siccome x ↔ y , esiste un cammino y → x I al momento della scoperta di r , tutti gli altri vertici della cfc sono bianchi I quindi esiste un cammino z → y → x I tutti i nodi raggiungibili da r saranno discendenti di r nell’albero DFS I z↔x z x y Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I un esempio: visitiamo il grafo a partire da A I gli alberi della foresta di scoperta si possono potare in modo da separare le B A cfc B A A D C D A D C D E F E F B E B E C F C F I questo è sempre possibile: I 3 cfc: {A},{D, B, C},{E, F } I sia u discendente di v in un albero della DFS e u = v I nello stesso albero ci sono nodi di più cfc I discendenti di u non possono appartenere al cfc di v I con una visita a partire dal nodo B la foresta di scoperta contiene due alberi di I per assurdo, se k è discendente di u e k ↔ v allora esistono i cammini v → u (u è discendente di v ) e anche u → v (tramite k che è discendente u ed e cui il primo contiene i nodi B,C,D,E e F (e quindi contiene nodi di 2 cfc) e il mutuamente raggiungibile con v ) e quindi non è vero che u = v E secondo solo il nodo A Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I basterebbe trovare un ordine “giusto” per quanto riguarda la scelta del nodo I gli alberi implicano l’esistenza di cammini in una direzione (se u è bianco da dove fare (ri)partire la visita per ottenere una foresta di scoperta in discendente di v in un albero allora nel grafo esiste un cammino da v ad u) cui ogni albero corrisponde ad una cfc I dobbiamo verificare l’esistenza di cammini nell’altra direzione I ordine giusto per scegliere fra i nodi bianchi: E, F , D, B, C, A I idea naturale: utilizziamo il grafo trasposto B E D A A D C F B E F C I ma non conosciamo l’ordine “giusto” Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I grafo G e suo trasposto GT : I grafo e suo trasposto: B B B B A D C A D C A D C A D C E F E F E F E F I naturalmente anche per il grafo trasposto A E I DFS del grafo trasposto col vertici in ordine alfabetico per quanto riguarda la scelta del nodo bianco da dove fare (ri)partire la visita: esiste un ordine non “giusto”: A, E, B, C, D, F D F A B E C D F B C Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I idea continua: troviamo l’ordine (sempre per quanto riguarda la scelta del I consideriamo il caso 1 bianco) della visita del grafo trasposto sfruttando informazioni ottenuti durante I y è discendente di x in un albero della foresta: la prima visita u I dati due nodi x e y , quale visitare per primo nel grafo trasposto? I assumiamo x = y e dunque vogliamo che i due nodi finiscano in due alberi x distinti della foresta y I dopo la prima DFS due casi sono possibili: 1. x è discendente di y in un albero della foresta (o viceversa: y è discendente di x) I esiste un cammino da x a y 2. x e y non sono discendenti uno dell’altro (sono in alberi distinti o su rami distinti) I se x = y allora I non esiste cammino da y a x in G I non esiste cammino da x a y in GT Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I consideriamo il caso 2 I in entrambi i casi conviene iniziare la visita di GT da x perchè, se i vertici non I x e y non sono discendenti uno dell’altro sono nella stessa cfc, non saranno collocati nello stesso albero I sembra che i vertici nella visita di GT debbano essere considerati: I dall’alto verso il basso x I da destra verso sinistra y I può esistere un cammino da x a y (archi di attraversamento) I se x = y allora I non esiste cammino da y a x in G I non esiste cammino da x a y in GT Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 30 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 30 3. Algoritmo basato su DFS 3. Algoritmo basato su DFS I gli intervalli di attivazione dei due vertici nei due casi: I dalle osservazioni precedenti ricaviamo l’algoritmo: 1. x.d