componenti fortemente connesse

(1)

F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)

Grafi:

componenti fortemente connesse

“Che cosa” sono e “come” si calcolano

………..

(2)

Che cosa sono

le componenti fortemente connesse

(di un grafo orientato)

(3)

Definizione di componenti fortemente connesse

Definizione. Le componenti fortemente connesse di un grafo orientato G = (V,E) sono le classi della relazione di equivalenza su V × V “mutuamente raggiungibile”.

Notazione. Useremo la notazione u ≈_FCv per indicare che i vertici u e v sono nella stessa classe di equivalenza.

Proprietà. In un grafo orientato G = (V,E), la relazione su V × V “mutuamente raggiungibile” è una relazione di equivalenza .

(4)

Un algoritmo per il calcolo

delle componenti fortemente connesse

(di un grafo orientato)

(5)

F. Damiani - Alg. & Lab. 04/05

Calcolo della componente fortemente connessa di un vertice Sia x un vertice di un grafo orientato G=(V,E).

1. Calcola i discendenti di x, ovvero l’insieme D(x) dei vertici di G che sono raggiungibili da x.

2. Calcola gli antenati di x, ovvero l’insieme A(x) dei vertici di G da cui x è raggiungibile.

3. Calcola l’intersezione di D(x) e D(y).

La complessità in tempo è O(|V| + |E|), infatti per il passo:

1. È sufficiente una visita a partire da x (costo O(|V| + |E|)) marcando opportunamente i vertici raggiunti.

2. e 3. È sufficiente calcolare il grafo trasposto di G, ovvero il grafo in cui tutti gli archi sono invertiti, (costo O(|V| + |E|)) e effettuare una visita a partire da x (costo O(|V| + |E|))

collezionando i vertici marcati al passo 1.

(6)

Calcolo di tutte le componenti fortemente connesse Sia G=(V,E) un grafo orientato.

Per ogni vertice x di G non ancora marcato

calcola la componente fortemente connessa di x marcandone tutti i vertici.

La complessità in tempo è O(|V|² + |V| *|E|).

(7)

F. Damiani - Alg. & Lab. 04/05

Un altro algoritmo per il calcolo

delle componenti fortemente connesse

(di un grafo orientato)

(8)

Due proprietà

Lemma 1. Se due vertici x, y di un grafo sono in una stessa c.f.c., allora nessun cammino tra di essi può abbandonare tale c.f.c.

Dimostrazione. Siano x e y t.c. x ≈_FCy. Sia z t.c. esiste un cammino x → z → y.

Siccome y ≈_FCx, esiste un cammino y → x. Quindi esiste un cammino z → y → x e, per definizione di c.f.c., z ≈_FCx.

Teorema 1. In una qualunque DFS di un grafo G orientato tutti i vertici di una c.f.c. vengono collocati in uno stesso albero.

Dimostrazione. Sia r il primo vertice di una data c.f.c. che viene scoperto nella DFS.

Poichè r è il primo, al momento della scoperta di r tutti gli altri vertici della c.f.c.

saranno bianchi. Inoltre, tutti i cammini da r agli altri vertici della c.f.c. conterranno solo vertici bianchi (perchè, per il Lemma 1, non lasciano mai la c.f.c.). Allora, per il Teorema del cammino bianco, tutti questi vertici saranno discendenti di r nell’albero DFS.

(9)

D

B

C

E

F A

N.B. Nello stesso albero ci sono vertici di più componenti fortemente connesse

Le c.f.c.del grafo sono tre: {A}, {D, B, C}, {E, F}

D

B C

E

F A

Esempio

Visitiamo il grafo a partire da A

(10)

L’albero può essere “potato” in modo da separare le componenti

D

B

C

E

F A

Si noti che questo è sempre possibile perchè se in un albero della foresta u è discendente di v e u ≈_FCv, allora ogni discendente t di u, non può appartenere alla stessa componente fortemente connessa cui appartiene v.

D

B C

E

F A

(11)

Come identificare i sottoalberi che costituiscono una c.f.c. ?

In realtà basterebbe trovare un “giusto” ordinamento per visitare i vertici per ottenere immediatamente gli alberi separati.

Nell’esempio precedente

D

B C

E

F A

un ordine “giusto” potrebbe essere:

E F D B C A

(12)

E F D B C A

D

B C

E

F A

Infatti una DFS del grafo, considerando i vertici nell’ordine produce la foresta:

D

B

C E

F

A

(13)

Torniamo allora all’idea di identificare, in ogni albero della foresta costruita da una DFS sul grafo G, i sottoalberi che costituiscono una c.f.c.

Ma quell’ordine non ci è noto !

(14)

Come identificare i sottoalberi che costituiscono una c.f.c. ?

Verifichiamo l’esistenza di quelli nell’altra direzione.

Un modo può essere quello di cercare i cammini nel grafo trasposto

Idea

Una DFS su G verifica l’esistenza di cammini in una direzione.

(15)

Riprendiamo l’esempio e costruiamo il grafo trasposto

D

B C

E

F

G A

D

B C

E

F A

G^T

Una DFS su G^T considerando i vertici in ordine alfabetico produce la seguente foresta:

A B C

D

E F

(16)

Anche sul grafo trasposto non tutte le DFS separano le componenti fortemente connesse.

Infatti, visitando prima E e poi D, si avrebbe:

A E

D B D F

B C

E

F A

C

E le componenti non sono ancora separate

!

(17)

Dati due vertici x e y, quale visitare per primo nel grafo trasposto?

Assumiamo . Dopo la DFS sul grafo G si possono presentare i seguenti due casi :

1. y è discendente di x in un albero della foresta (o viceversa x è discendente di y)

2. x e y non sono uno discendente dell’altro (sono in alberi o sottoalberi distinti della foresta)

x ≈_FCy

Idea (continua): nella seconda visita potremmo

trovare l’ordine di visita per i vertici sfruttando informazioni che si possono ottenere durante la prima visita.

(18)

Consideriamo il caso 1.

y è discendente di x in un albero della foresta DFS(G) u

x

y

Esiste in G un cammino da x a y, ma se x ≈_FCy non deve esistere il cammino da y a x in G, cioe` da x a y in G^T.

(19)

Nel caso 2.

x e y non sono uno discendente dell’altro

y

puo`esistere un cammino da x a y (a causa di archi

di attraversamento), ma se x ≈_FCy non deve esistere nessun cammino da y a x in G, cioe` nessun cammino da x

a y in G^T.

x

(20)

Sembra allora che i vertici nella visita di G^Tdebbano essere considerati:

• dall’alto verso il basso, e

• da destra verso sinistra

In entrambi i casi allora sarà “sicuro” iniziare la visita di G^T da x perchè, se i vertici non sono nella stessa c.f.c., non

verranno collocati nello stesso albero.

(21)

Osserviamo gli intervalli di attivazione dei due vertici nel caso 1 si ha:

d[x] d[y] f[y] f[x]

nel caso 2 si ha:

d[y] f[y] d[x] f[x]

In entrambi i casi f[x] > f[y]

i vertici vanno considerati in ordine decrescente di

tempo di fine visita

(22)

Dalle osservazioni precedenti ricaviamo il seguente algoritmo Strongly-Connected-Components (G)

1. Visita G con l’algoritmo DFS-VISITA-TUTTI-I-VERTICI e costruisci una lista dei vertici

in ordine decrescente dei tempi di fine visita 2. Costruisci G^T

3. Visita G^T con l’algoritmo DFS-VISITA-TUTTI-I-VERTICI considerando, nel ciclo principale dell’algoritmo, i vertici

nell’ordine trovato al passo 1.

Complessita`: O(V+E)

Un algoritmo per il calcolo delle componenti fortemente connesse

(23)

Lemma 2. Un grafo orientato e il suo trasposto hanno le stesse c.f.c.

Dimostrazione. Immediata dalla definizione di c.f.c.

Lemma 3. Sia A un albero ottenuto con la visita in profondita`

di G^T, considerando i vertici in ordine decrescente dei tempi di fine visita su G, e sia u la sua radice.

Per ogni vertice v discendente di u: v ≈_FCu Teorema 1. In una qualunque DFS di un grafo G orientato

tutti i vertici di una c.f.c. vengono collocati in uno stesso albero.

Per dimostrare che l’algoritmo e` corretto abbiamo bisogno del Teorema 1 (gia` dimostrato):

e dei seguenti lemmi:

Dimostrazione della correttezza dell’algoritmo

(24)

Lemma 3. Sia A un albero ottenuto con la visita in profondita`

di G^T, considerando i vertici in ordine decrescente dei tempi di fine visita su G, e sia u la sua radice.

Per ogni vertice v discendente di u: v ≈_FCu

Dimostrazione.

Dimostriamo prima di tutto che ogni discendente di u in A è anche un discendente di u in un albero della foresta costruita dalla visita in profondita’ su G.

La dimostrazione e’ fatta per assurdo.

Consideriamo un cammino sull'albero A a partire dalla radice u;

sia v il primo vertice sul cammino per cui il lemma non vale e sia w il suo predecessore sul cammino.

(25)

Poiche’ v è il primo vertice per cui il lemma non vale, l'enunciato vale per w, e quindi:

d[u] ≤ d[w] < f[w] ≤ f[u] (w può anche essere u) v

A u

w

Siccome la visita DFS(G^T) considera i vertici in ordine

decrescente di fine visita, per ogni discendente di u in A, e quindi in particolare per v, vale

f[v] < f[u]

(26)

Per il teorema delle parentesi, se v non è un discendente di u nella prima visita, i due intervalli di visita di v e u devono essere disgiunti, cioè deve valere:

d[v] < f[v] < d[u] < f[u]

d[v] f[v] d[u] d[w] f[w] f[u]

Impossibile!

v è adiacente a w in G^T w è adiacente a v in G, e la visita di v non puo’ terminare prima che sia iniziata la visita di un suo adiacente, cioe’ f[v] non puo’ precedere d[w].

(27)

Siccome v è discendente di u in A, esiste un cammino da u a v in G^T, e quindi da v a u in G. D'altra parte, per cio’ che

abbiamo appena dimostrato, in G esiste anche un cammino da u a v, cioe’ v ≈_FCu .

Osservazione: si noti che per la dimostrazione del Lemma 3 è essenziale che la visita DFS(G^T) consideri i vertici in ordine decrescente di fine visita.

Concludiamo la dimostrazione del lemma 3:

(28)

I lemmi permettono di dimostrare che ogni albero della

foresta ottenuta con la visita in profondita` di G^T contiene :

•

tutti

i vertici di una c.f.c. di G (Teorema 1 e Lemma 2)

•

solo

i vertici di una c.f.c. di G (Lemma 3)

L’algoritmo Strongly-Connected-Components e`

corretto

ossia, quando applicato ad un grafo orientato, restituisce una foresta i cui alberi individuano le componenti

fortemente connesse del grafo.

(29)

Strongly-Connected-Components (G)

1. Visita G con l’algoritmo DFS-VISITA-TUTTI-I-VERTICI e costruisci una lista dei vertici

in ordine decrescente dei tempi di fine visita 2. Costruisci G^T

3. Visita G^T con l’algoritmo DFS-VISITA-TUTTI-I-VERTICI considerando, nel ciclo principale dell’algoritmo, i vertici

nell’ordine trovato al passo 1.

{ G grafo orientato }

{ Gli alberi della foresta ottenuta rappresentano le componenti fortemente connesse di G}

In conclusione

(30)

componenti fortemente connesse

Grafi: