Grafi: Componenti Fortemente Connesse - PDF

Document Details

SteadyBoltzmann

Uploaded by SteadyBoltzmann

Università di Torino

Ugo de’Liguoro, András Horváth

Tags

componenti fortemente connesse algoritmi strutture dati informatica

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

Use Quizgecko on...
Browser
Browser