algoritmul lui prim - competentedigitale.ro · calin jebelean algoritmul lui kruskal 1 algoritmul...

20
Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru un graf ponderat (graf in care fiecare arc are asociat un cost) Un arbore de acoperire pentru un graf este un subgraf alcatuit din toate nodurile grafului initial dar nu din toate arcele, ci doar din atatea arce cat sa nu apara cicluri (altfel nu ar fi arbore)

Upload: others

Post on 01-Sep-2019

212 views

Category:

Documents


7 download

TRANSCRIPT

Page 1: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 1

Algoritmul lui Kruskal

Este un algoritm care returneaza un arbore de acoperire minim pentru un graf ponderat (graf in care fiecare arc are asociat un cost)

Un arbore de acoperire pentru un graf este un subgraf alcatuit din toate nodurile grafului initial dar nu din toate arcele, ci doar din atatea arce cat sa nu apara cicluri (altfel nu ar fi arbore)

Page 2: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 2

Algoritmul lui Kruskal

Trebuie sa conectam 3 orase la o retea telefonica: Bucuresti, Timisoara si Arad

Necesar cablu: 1300 km

60

600

640

Page 3: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 3

Algoritmul lui Kruskal

E inutil sa executam toate cele trei conexiuni, numai doua din ele sunt suficiente pentru o comunicare in bune conditii intre oricare 2 orase

De exemplu, legatura Timisoara – Arad ar putea lipsi, caz in care necesarul de cablu devine 1240 km

600

640

Page 4: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 4

Algoritmul lui Kruskal

Sau legatura Timisoara – Bucuresti ar putea lipsi, necesarul de cablu devenind 700 km

60640

Page 5: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 5

Algoritmul lui Kruskal

Oricare 2 legaturi sunt suficiente, deoarece semnalul electric circula suficient de rapid ca un abonat din Timisoara care doreste sa vorbeasca cu unul din Arad (de exemplu) sa nu-si dea seama ca nu exista legatura directa intre Timisoara si Arad si ca apelul sau este rutat prin Bucuresti

Din punctul de vedere al necesarului de cablu, lucrurile nu mai stau la fel

Conteaza foarte mult care legaturi vor fi realizate si care nu

Cel mai ieftin ar fi sa alegem legaturile Arad – Timisoara si Timisoara – Bucuresti si sa evitam legatura Arad - Bucuresti, necesarul de cablu ajungand in acest caz la 660 km; aceasta este situatia optima – sau “acoperirea minima” a retelei

Page 6: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 6

Algoritmul lui Kruskal

Se observa ca trebuie determinat un arbore de acoperire pentru graful initial, adica un subgraf continand toate nodurile grafului insa doar atatea arce cat sa ramana un arbore (trebuie evitate ciclurile)

Pentru un graf conex cu N noduri, un arbore de acoperire va avea N-1 arce (2 arce in cazul grafului Arad – Timisoara –Bucuresti discutat)

60

600

640

Page 7: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 7

Algoritmul lui Kruskal

Cazurile cele mai simple sunt cele ale grafurilor conexe, adica acelea in care din orice nod se poate ajunge in orice alt nod

In figura de mai jos este prezentat un graf neconex alcatuit din 2 componente conexe, care n-au legatura una cu alta

Cu alte cuvinte, in graful de mai jos nu se poate ajunge din orice nod in orice alt nod (daca nodurile sunt in componente conexe diferite)

Page 8: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 8

Algoritmul lui Kruskal

Pentru un graf conex pot fi gasiti mai multi arbori de acoperire, in functie de arcele care sunt alese pentru a forma arborele

Costul total al arborelui de acoperire este dat de suma costurilor arcelor alese, deci vom avea arbori “mai scumpi” si arbori “mai ieftini”

Algoritmul lui Kruskal gaseste arborele de acoperire cel mai ieftin pentru un graf conex ponderat, pe care-l vom numi “arborele de acoperire minim” (acesta poate sa nu fie unic)

Daca graful nu este conex, el este alcatuit din subgrafuri (componente) conexe

In cazul unui astfel de graf, algoritmul lui Kruskal gaseste cate un arbore de acoperire minim pentru fiecare componenta conexa a grafului (neconex) dat, adica o “padure de arbori de acoperire minimi”

Page 9: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 9

Algoritmul lui Kruskal

Se lucreaza cu mai multe multimi de noduri

Initial, se porneste de la N multimi a cate un nod, astfel incat fiecare nod al grafului sa faca parte din cate o multime (N este numarul de noduri din graf)

La fiecare pas se selecteaza cel mai ieftin arc din graf care conecteaza noduri din multimi diferite

Daca un astfel de arc nu exista, algoritmul se incheie

Dupa selectia arcului, cele doua multimi din care fac parte extremitatile sale se inlocuiesc cu reuniunea lor, numarul total de multimi scazand cu o unitate

Consecinta este ca algoritmul se va opri atunci cand numarul de multimi ajunge egal cu numarul de componente conexe ale grafului (o singura multime in cazul grafurilor conexe)

Page 10: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 10

Algoritmul lui Kruskal

Fie graful din figura

Cel mai ieftin arc din graf care leaga noduri din multimi diferite este D-H de cost 1

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 8:

{A} {E}

{B} {F}

{C} {G}

{D} {H}

Page 11: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 11

Algoritmul lui Kruskal

Sunt 3 arce viabile: A-B, D-G si G-H

Se alege arbitrar arcul A-B

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 7:

{A} {E}

{B} {F}

{C} {G}

{D, H}

Page 12: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 12

Algoritmul lui Kruskal

Sunt 2 arce viabile: D-G si G-H

Se alege arbitrar arcul D-G

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 6:

{A, B} {E}

{C} {F}

{D, H} {G}

Page 13: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 13

Algoritmul lui Kruskal

Arcul G-H, desi cel mai ieftin din graf, este ignorat, deoarece uneste noduri din aceeasi multime

Se alege arcul A-D

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 5:

{A, B} {E}

{C} {F}

{D, G, H}

Page 14: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 14

Algoritmul lui Kruskal

Se alege arcul C-F

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 4:

{A, B, D, G, H} {E}

{C} {F}

Page 15: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 15

Algoritmul lui Kruskal

Se alege arcul B-E

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 3:

{A, B, D, G, H} {E}

{C, F}

Page 16: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 16

Algoritmul lui Kruskal

Se alege arcul F-H

29

4

6

3

1

5

3

7

4

8 2

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 2:

{A, B, D, E, G, H} {C, F}

Page 17: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 17

Algoritmul lui Kruskal

Algoritmul se incheie deoarece nu se mai poate gasi un arc care conecteaza noduri din multimi diferite (fiind o singura multime)

2

4

3

1

3

4

A

B

C

D

E

F

G

H

2

Multimile sunt in numar de 1:

{A, B, C, D, E, F, G, H}

Arborele de acoperire este cel din figura alaturata, costul sau fiind 19

Nu exista un arbore de acoperire mai ieftin pentru graful dat

Page 18: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 18

Algoritmul lui Kruskal

Conditia de oprire a algoritmului este imposibilitatea gasirii unui arc care conecteaza noduri din multimi diferite

Aceasta conditie este indeplinita implicit atunci cand s-a ajuns la o singura multime

Daca graful nu este conex, atunci nu se va ajunge niciodata la o singura multime

Totusi, cand numarul de multimi ajunge egal cu numarul de componente conexe din graf (>1 pentru un graf neconex), atunci nu se mai poate gasi un arc care conecteaza noduri din multimi diferite, deci algoritmul se incheie in conformitate cu conditia de oprire enuntata

Se recomanda studierea exemplului urmator pentru edificare

Page 19: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 19

Algoritmul lui Kruskal

Aplicand algoritmul lui Kruskal pentru graful neconex din figura, se ajunge in situatia prezentata: 2 arbori de acoperire (o padure), cate unul pentru fiecare componenta conexa a grafului

Multimile sunt: {A, B, C, E} {D, F, G, H} – 2 multimi, tot atatea cate componente conexe are graful

29

4

1

54

8 2

A

B

C

D

E

F

G

H

2

Page 20: Algoritmul lui Prim - competentedigitale.ro · Calin Jebelean Algoritmul lui Kruskal 1 Algoritmul lui Kruskal Este un algoritm care returneaza un arbore de acoperire minim pentru

Calin Jebelean Algoritmul lui Kruskal 20

Algoritmul lui Kruskal

Prin insasi natura neconexa a grafului, algoritmul nu mai poate gasi nici un arc (cu atat mai mult nu poate gasi un arc minim) care conecteaza noduri din multimi diferite

Daca un astfel de arc ar exista, graful nu ar fi neconex, ci acel arc ar fi legatura intre cele doua grupuri de noduri care formeaza acum cele doua componente conexe ale grafului

Neexistand arcul necesar continuarii algoritmului, acesta se opreste si rezultatul este dat de arcele ingrosate din figura de pe slide-ul anterior