proiectarea algoritmilor 11. componente tare...

Platformă de e-learning și curriculă e-content pentru învățământul superior tehnic

Proiectarea Algoritmilor

11. Componente tare conexe

Proiectarea Algoritmilor 2010

Bibliografie

Giumale – Introducere in Analiza

Algoritmilor cap. 5.2

Cormen – Introducere în Algoritmi cap.

23.5

http://en.wikipedia.org/wiki/Tarjan%27s_st

rongly_connected_components_algorithm

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm


Componente Tare Conexe (CTC)

Definiție: Fie G = (V,E) un graf orientat. G este tare-conex ⇔ u,vV o cale u..v si o cale v..u (uR(v) && vR(u)).

Definiție: G = (V,E) graf orientat. G’ = (V’,E’), V’⊆V, E’⊆E. G’ este o CTC a lui G ⇔ G’ e tare-conex ( u,vV’, uR(v) && vR(u)) si G’ este maximal.

Lema 5.6: G = (V,E) graf orientat, G’ CTC, u,vV’ => u..v din G are noduri exclusiv in V’

Dem: z a.i. u..z..v => zR(u) si vR(z). Dar uR(v) => zR(v) => v si z sunt in aceeași CTC.


Exemplu (I) – determinare CTC

K

L

A

B

C

D

E

F

G

H

I

J


Exemplu (II) – determinare CTC(2)

K

L

A

B

C

D

E

F

G

H

I

J A

B

C

D

E

F

G

H

I

J

K

L



Teorema 5.10: G = (V,E) orientat, G’ =

(V’,E’) o CTC a lui G. Toate nodurile

vV’ sunt grupate in același Arb(u)

construit de DFS(G), unde u este primul

nod descoperit al componentei.

Dem: vV’, v ≠ u, u..v drum cu noduri

albe la momentul descoperirii d(u); toate

nodurile drumului sunt in V’ (conf. Lema 5.6)

=> (din Teorema drumurilor albe) v este

descendent al lui u in Arb(u)


Exemplu (III) – DFS

K

L

A

B

C

D

E

F

G

H

I

J

A

B

C

D

E

F

G

H

I

J

K

L

Aplicare DFS pornind din primul nod al fiecarei CTC


Exemplu (IV) - DFS(2)

A

B

C

D

E

F

G

H

I

J

K

L

Conform Teoremei

nodurile din aceeași

CTC sunt grupate in

același arbore DFS!

A

1/16

B

2/15

C

3/10

D

5/6

E

4/9

F

7/8

G

11/14

H

12/13

I

17/24

J

18/23

K

19/22

L

20/21

I

17/24

J

18/23

K

19/22

G

11/14

A

1/16

H

12/13

B

2/15

C

3/10

D

5/6

E

4/9



Definiție: G = (V,E) orientat, uV. (u) = strămoș DFS al

lui u determinat in cursul DFS(G) dacă:

(u)R(u)

f((u)) = max{f(v) | vR(u)}

Ce e (u)?

Teorema 5.11: (u) satisface următoarele proprietăți:

1. f(u) f((u)) când e egalitate?

2. vR(u), f((v)) f((u)) ce înseamnă ca e egalitate?

3. ((u)) = (u) Dem:

(u) este primul nod din CTC descoperit de DFS(G)

u este primul nod din CTC

u si v sunt in aceeași CTC 2

1 ((u))R((u)) f(((u))) f((u)) și

f(((u))) ≥ f((u)) f(((u))) = f((u)) ((u)) = (u)


Exemplu (V) – stramosi

A

1/16

B

2/15

C

3/10

D

5/6

E

4/9

F

7/8

G

11/14

H

12/13

I

17/24

J

18/23

K

19/22

L

20/21

I

17/24

J

18/23

K

19/22

G

11/14

A

1/16

H

12/13

B

2/15

C

3/10

D

5/6

E

4/9

A, C, I sunt strămoși DFS ai nodurilor din

componenta conexă din care fac parte.

Proprietățile strămoșilor:

•f(u) f((u))

Ex: f(B) f((B)) = f(A)

• vR(u), f((v))f((u))

Ex: ER(B), f(C) = f((E)) f((B)) = f(A)

•((u)) = (u)

Ex: ((E)) = (C) = C = (E)



Din Definiție: (u)R(u) && f((u)) = max{f(v) | vR(u)}.

Teorema 5.12. G = (V,E) orientat, uV, u este descendent al

lui (u) in Arb((u)) construit de DFS.

Dem: prin considerarea tuturor culorilor posibile ale lui (u) la

momentul d(u).

Teorema 5.13. G = (V,E) orientat, u,vV; u si v aparțin

aceleiași CTC ⇔ (u) = (v).

Dem folosind proprietățile strămoșilor :

u,v aceleiași CTC => (u) = (v): vR(u), f((v)) f((u)) si uR(v),

f((u)) f((v)) => f((u)) = f((v)) (u) = (v)

(u) = (v) => (u)R(u) => u si (u) aceleiași CTC

si (u)R(v) => v si (u) aceleiași CTC

=> u si v aceleiași CTC


Exemplu (VI)

A

1/16

B

2/15

C

3/10

D

5/6

E

4/9

F

7/8

G

11/14

H

12/13

I

17/24

J

18/23

K

19/22

L

20/21

A

G

B

H

C

D

E

F

I

J

K

L

Primul nod dintr-o CTC descoperit la

DFS va avea copii in arborele

generat de DFS toate elementele

componentei conexe!



Probleme:

trebuie să eliminăm nodurile care nu sunt în componenta conexă.

vrem ca fiecare arbore construit să conțină o CTC.

Idee – eliminăm nodurile ce nu aparțin CTC! Cum?

Dacă aparțin Arb(u) și nu CTC => u..v si ∄ v..u.

DFS pe graful transpus, în ordinea inversă a timpilor de finalizare obținuți din DFS pe graful normal!


Exemplu (VII) – DFS (GT)

A

1/16

B

2/15

C

3/10

D

5/6

E

4/9

F

7/8

G

11/14

H

12/13

I

17/24

J

18/23

K

19/22

L

20/21


Exemplu (VIII) – DFS (GT) (2)

A

1/16

B

2/15

C

3/10

D

5/6

E

4/9

F

7/8

G

11/14

H

12/13

I

17/24

J

18/23

K

19/22

L

20/21

L

7/8

A

9/16

B

12/13

C

17/22

D

18/21

E

19/20 F

23/24

G

11/14

H

10/15

I

1/6

J

3/4

K

2/5



Cazuri in DFS(GT):

v este in CTC descoperita din u v

poate fi descoperit din u si in

DFS(GT).

vCTC dar vArb(u) in DFS(G)

nu va fi atins in DFS(GT) din u.

vCTC dar v..u in G f(v) > f(u)

v va fi deja colorat in negru când

se explorează u.

A

9/16

B

12/13 H

10/15

G

11/14

A

9/16

G

11/14

I

1/6

J

3/4

C

17/22

D

18/21

E

19/20 F

23/24


Observatii

Înlocuind componentele tare conexe cu noduri obținem un graf aciclic. De ce?

Pentru că altfel am avea o singură CTC!

Prima parcurgere DFS este o sortare topologică. De ce?

Pentru că sortează nodurile in ordinea inversă a timpilor!


Pseudocod algoritm CTC

Algoritmul lui Kosaraju:

CTC(G)

DFS(G)

GT = transpune(G)

DFS(GT) (in bucla principală se tratează nodurile în ordinea

descrescătoare a timpilor de finalizare de la primul DFS)

Componentele conexe sunt reprezentate de pădurea de

arbori generați de DFS(GT).

Complexitate?


Algoritmul lui Kosaraju

Complexitate

O(n+m) n = numar noduri

m = numar muchii

Corectitudine algoritm CTC (1)

Teoremă: Algoritmul CTC calculează corect

componentele tare conexe ale unui graf G = (V,E).

Dem. prin inducție după nr. de arbori de adâncime

găsiți de PAD a GT că vârfurile din fiecare arbore

formează o CTC:

Fiecare pas demonstrează ca arborele format in acel pas

e o CTC, presupunând că toți arborii produși deja sunt

CTC.

P1: trivial pt. că ∄ arbori anteriori.

Pn Pn+1: Fie arborele T obținut in pasul curent având

rădăcina r. Notăm Cr = {vV | (v) = r}.


Corectitudine algoritm CTC (2)

Demonstrăm că u T ⇔ uCr:

⟹ uCr r..u toate nodurile din Cr ajung in

același arbore de PAD. Dar rCr si r e rădăcina lui T

∀ uCr => uT

⟸ demonstrăm că ∀ w a.i. f((w)) > f(r) sau f((w)) <

f(r), w T

Dacă f((w)) > f(r) la d(r), w e deja pus in CTC cu

rădăcina (w) pt. că nodurile sunt considerate in ordinea

inversa a timpilor de finalizare w T

Dacă f((w)) < f(r) w T pt. că altfel (wT) r..w in GT

w..r in G rR(w), f((w)) ≥ f((r)) = f(r) (F)

T conține doar nodurile pt. care (w) = r T = Cr


proiectarea algoritmilor 11. componente tare...

Documents