Arbori partiali de cost minim

Fie G = <X, V> un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor.Un arbore este un asemenea graf ce nu are cicluri. Fiecare muchie are un cost pozitiv (sau o lungime pozitiva). Pentru a gasi un arbore se pune problema sa gasim o submultime A inclusa in U, astfel incat toate varfurile din X sa ramina conectate atunci cand sunt folosite doar muchii din A.Numim arbore partial de cost minim acel arbore ce are multimea varfurilor X si a muchiilor A iar suma lungimilor muchiilor din A este minima.Cautam deci o submultime A de cost total minim care sa lege printr-un drum oricare doua noduri din X. Aceasta problema se mai numeste si problema conectarii oraselor cu cost minim, avand numeroase aplicatii.

Problema conectarii oraselor de cost minim:Se dau n orase precum si costul conectarii anumitor perechi de orase.Se cere sa se eleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total sa fie minim.

Graful partial <X, A> este un arbore si este numit arborele partial de cost minim al grafului G (minimal spanning tree). Un graf poate avea mai multi arbori partiali de cost minim si acest lucru se poate verifica pe un exemplu.Vom prezenta doi algoritmi greedy care determina arborele partial de cost minim al unui graf. In terminologia metodei greedy, vom spune ca o multime de muchii este o solutie, daca constituie un arbore partial al grafului G, si este fezabila, daca nu contine cicluri. O multime fezabila de muchii este promitatoare, daca poate fi completata pentru a forma solutia optima. O muchie atinge o multime data de varfuri, daca exact un capat al muchiei este in multime. Urmatoarea proprietate va fi folosita pentru a demonstra corectitudinea celor doi algoritmi.

Multimea initiala a candidatilor este V. Cei doi algoritmi greedy aleg muchiile una cate una intr-o anumita ordine, aceasta ordine fiind specifica fiecarui algoritm.

1 Algoritmul lui Kruskal

Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu. Alegem astfel X-1 muchii. Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat?

Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: , , , , , , , , , , , si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1.

Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile , , , , , . La fiecare pas, graful partial <X, A> formeaza o padure de componente conexe, obtinuta din padurea precedenta unind doua componente. Fiecare componenta conexa este la randul ei un arbore partial de cost minim pentru varfurile pe care le conecteaza. Initial, fiecare varf formeaza o componenta conexa. La sfarsit, vom avea o singura componenta conexa, care este arborele partial de cost minim cautat (Figura 1b).Ceea ce am observat in acest caz particular este valabil si pentru cazul general.

In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim.

2 Algoritmul lui Prim

Cel de-al doilea algoritm greedy pentru determinarea arborelui partial de cost minim al unui graf se datoreaza lui Prim (1957). In acest algoritm, la fiecare pas, multimea A de muchii alese impreuna cu multimea X a varfurilor pe care le conecteaza formeaza un arbore partial de cost minim pentru subgraful <X, A> al lui G. Initial, multimea W a varfurilor acestui arbore contine un singur varf oarecare din X, care va fi radacina, iar multimea A a muchiilor este vida. La fiecare pas, se alege o muchie de cost minim, care se adauga la arborele precedent, dand nastere unui nou arbore partial de cost minim (deci, exact una dintre extremitatile acestei muchii este un varf in arborele precedent). Arborele partial de cost minim creste "natural", cu cate o ramura, pina cand va atinge toate varfurile din X, adica pina cand W = X. Functionarea algoritmului, pentru exemplul din Figura 6.1a, este ilustrata in Tabelul 2. La sfarsit, A va contine aceleasi muchii ca si in cazul algoritmului lui Kruskal.

Descrierea algoritmului este data in continuare.

Pentru a obtine o implementare simpla, presupunem ca: varfurile din X sunt numerotate de la 1 la n, X = ; matricea simetrica C da costul fiecarei muchii, cu C[i, j] = maxint, daca muchia nu exista. Folosim doi vectori,vectorul parintilor T[i] si un vector s[i].

Vectorul T este vectorul tata in care ,pentru fiecare nod i din X,T[i] este egal cu parintele lui i.

Vectorul S este definit astfel:

S[i]= 0 daca i apartine arborelui partial construit pana atunci

K daca :- i nu apartine arborelui partial deja construit

-muchia de cost minim care uneste i cu un nod din graful deja construit este [i,k]

cu k neapartinand arborelui partial

Initial vectorul tata este 0 peste tot iar vectorul S este definit astfel:S[v]=0 si S[i]=v pentru i<>v,unde v este varful arborelui.Se alege apoi muchia de cost minim (i,j) care are numai o extremitate in arborele partial construit adica S[i]=0 iar S[j]<>0.Se reactualizeaza cei doi vectori:vectorul S pentru j adica S[j]=0 iar vectorul tata T[j]=S[j].Se reia cautarea muchiei de cost minim daca nu au fost alese n-1 muchii.

2 2 3

3

1 5 1

(a) 2 Figura 2 (b)

1 4

4

4

Aplicand acest algoritm pentru graful din Figura 2.a,se vor urma pasii:

-n=5,a matricea de cost si varful

-se alege varful,de exemplu v=1 iar vectorii sunt:

S

T

-si ia i=2,n si se alege muchia de cost minim determinata de a[i,S[i]],(in acest caz se alege j=2).

-se reactualizeaza vectorii T si S;T[j]=S[j](T[2]=1) si S comparandu-se valoarea muchiei [i,S[i]] cu

cea a muchiei [i,j] si daca este mai mica se modifica S(S[i]=j) unde S[i]<>0 si j este ultimul varf introdus.Cei doi vectori vor fi:

S

T

-se cauta din nou muchia de cost minim si se repeta faza precedunta pana se aleg n-1 muchii(in cazul Figurii 2.a, 4 muchii).Vectorii vor suferii urmatoarele transformari:

1. S

T

2. S

T

3. S

T

-in final vectorul S va fi zero iar vectorul T va fi vectorul tata a arboreluipartial de cost minim.Costul arborelui(Figura 2.b) va fi 10.

Se cere sa se dea varful dar aceste poate fi luat intotdeauna 1 daca se cauta sa se afle numai costul arborelui deoarece,muchiile nefiind orientate, se obtine intotdeauna acelasi arbore.Cel ce difera este insa vectorul tata in funtie de varful de pornire dar acesta poate fi refacut dupa vectorul tata al grafului ce are varful 1.

Bucla principala se executa de n-1 ori si buclele for din interior necesita un timp in O(n). Algoritmul Prim necesita, deci, un timp in O(n²). Am vazut ca timpul pentru algoritmul lui Kruskal este in O(m log n). Pentru un graf dens (adica, cu foarte multe muchii), se deduce ca m se apropie de n(n-1)/2. In acest caz, algoritmul Kruskal necesita un timp in O(n² log n) si algoritmul Prim este probabil mai bun. Pentru un graf rar (adica, cu un numar foarte mic de muchii), m se apropie de n si algoritmul Kruskal necesita un timp in O(n log n), fiind probabil mai eficient decat algoritmul Prim.

Algoritmul lui Roy-Floyd (determinarea matricii drumurillor)

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii) memorat prin matricea ponderilor. Se cere ca pentru doua noduri x,y citite sa se determine lungimea minima a lantului de la x la y.

Astfel:

Initial matricea ponderilor pentru nodurile 1 si 4 va retine 10. Se observa ca lantul 1,2,3,4 determina o suma a costurilor mai mica: 2+3+1=6. Lungime minima a lantului de la 1 la 4 este 6.

Algoritmul:

-se genereaza matricea ponderilor:

Unde pinf reprezinta plus infinit

-se incearca pentru oricare pereche de noduri i,j sa se obtina "drumuri" mai scurte prin noduri intermediare k (kI1.n).

Acest lucru se determina comparand "lungimea" lantului a[i,j] cu lungimea lantului care trece prin k si daca:

a[i,j] > a[i,k]+a[k,j] atunci se atribuie: a[i,j] a[i,k]+a[k,j]

Astfel generarea matricii drumurilor optime se realizeaza cu urmatoarea secventa:

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if(a[i][j]>a[i][k]+a[k][j])

a[i][j]=a[i][k]+a[k][j];

Se obtine:

In continuare, dupa determinarea matricii lanturilor optime, pentru doua noduri citite x, y se cere sa se reconstituie un lant optim de la x la y (pot fi mai multe solutii).

Solutie:

-se determina daca exista un lant de la x la y (ar putea sa nu existe un astfel de lant daca graful nu este conex):

cand a[x,y]

-se descompune "drumul" de la x la y prin ca atunci cand: a[x][y]=a[x][k]+a[k][y];

-         pentru un astfel de algoritm se utilizeaza strategia Divide et Impera