Cuprins

Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.

Extras din document

CUPRINS
1. Introducere ........ 3
1.1. Retele de transport si fluxuri ............. 3
1.2. Exemplu de retea de transport ............ 5
1.3. Retele cu mai multe surse si destinatii .. 8
1.4. insumarea fluxului ........ 10
2. Metoda lui Ford-Fulkerson .. 12
2.1. Retele reziduale ........... 12
2.2. Drumuri de ameliorare 14
2.3. Taieturi in retele de transport ..... 16
2.4. Algoritmul de baza Ford-Fulkerson .......... 18
2.5. Analiza algoritmului Ford-Fulkerson ........ 21
3. Algoritmi de preflux 26
3.1. Aspecte intuitive .......... 26
3.2. Operatii de baza ........... 28
3.3. Algoritmul generic ....... 30
3.4. Corectitudinea metodei de preflux ............. 31
3.5. Analiza metodei de preflux ......... 33
4. Algoritmul mutare-in-fata ...... 37
4.1. Muchii si retele admisibile ........... 37
4.2. Liste de adiacenta .......... 39
4.3. Algoritmul mutare-in-fata ............ 44
4.4. Analiza algoritmului ..... 48
5. Aplicatie pentru algoritmul Mutare-in-fata .... 50
5.1. Codificarea datelor ...... 50
5.2. Rezultate obtinute ........ 51
Bibliografie
Anexa

Alte date

?1. INTRODUCERE

O ,,retea de transport” este o retea (retele de conducte de fluide, retele de canale, retele de strazi etc.) prin care se transporta diverse fluxuri de materiale. De exemplu se considera un material care este transportat intr-un sistem de la sursa unde este produs la destinatia unde este consumat. Daca ceea ce se produce la sursa, este consumat in acelasi ritm la destinatie, atunci, in orice punct al sistemului, “fluxul” retelei reprezinta viteza cu care materialul se deplaseaza prin retea. Din punct de vedere informatic, o retea de transport este un graf orientat caracterizat de unul sau mai multe puncte de intrare in retea si unul sau mai multe puncte de iesire din retea.

Retelele de transport pot modela curgerea lichidului in sisteme de conducte sau canale, deplasarea pieselor pe benzi rulante, scurgerea curentului prin retele electrice, deplasarea informatiilor prin retele de comunicatii etc.

Fiecare arc dintr-o retea de transport poate fi considerat drept conducta pentru transportul unui material. Fiecare conducta are o capacitate data, care este de fapt ritmul maxim cu care materialul se poate deplasa prin conducta. De exemplu, printr-o conducta pot curge cel mult 2m3/h de fluid.

Varfurile (nodurile) reprezinta jonctiunile conductelor si in afara varfurilor sursa si destinatie, materialul nu se poate acumula in nici un varf. Aceasta proprietate se numeste,,consevarea fluxului” si este identica cu legea conservarii masei care se aplica la bilantul de materiale sau cu legea lui Kirchoff in cazul curentului electric.

Problema determinarii fluxului maxim este cea mai simpla problema legata de retelele de transport, care cere sa se determine cantitatea maxima de material care poate fi transportata de la sursa la destinatie tinand cont de restrictiile de capacitate. Tehnicile de baza ale acestor algoritmi pot fi adaptate la rezolvarea altor tipuri de probleme in retele de transport.

Pentru rezolvarea problemelor de flux maxim se precizeaza in continuare urmatoarele:

- formalizarea notiunilor de retea de transport si a celei de flux in retea;

- definirea formala a problemei de flux maxim;

- metoda clasica Ford-Fulkerson pentru gasirea fluxului maxim;

- metoda preflux, care este metoda cea mai rapida la problemele de flux;

- o implementare particulara a algoritmului de preflux.

1.1. Retele de transport si fluxuri

O retea de transport G = (V,E) este un graf orientat, in care fiecarui arc (u,v)?E ii este asociata o capacitate nenegativa c(u,v)? 0. Daca (u.v)?E se considera ca c(u,v)=0.

Se disting doua varfuri in retea:

? un virf sursa s;

? un varf destinatie t.

Se presupune ca fiecare varf se gaseste pe cel putin un drum de la sursa la destinatie, adica, pentru orice varf v?V exista un drum s? v ? t. Graful este deci conex si ?E???V?- 1.

Definitia formala a fluxului

Fie G = (V,E) o retea de transport cu o functie de capacitate c. Fie s varful sursa si t varful destinatie. Fluxul in G este o functie f:V×V?R cu valori reale care satisface conditiile:

? Restrictia de capacitate;

? Antisimetrie;

? Conservarea fluxului.

Restrictie de capacitate:Pentru orice u,v?V exista f(u,v)?c(u,v)

Restrictia de capacitate impuse ca fluxul de la un varf la altul sa nu depaseasca valoarea capacitatii arcului dintre cele doua varfuri.

Antisimetrie: Pentru orice u,v?V exista f(u,v) = - f(u,v)

Antisimetria impune ca fluxul de la un varf u la un varf v sa fie egal cu opusul fluxului de la v la u. Astfel, fluxul de la un varf la el insusi este egal cu 0, deoarece pentru orice u?V exista f(u,u)= -f(u,u), care implica f(u,u)= 0

Conservarea fluxului: Pentru orice u?V – {s,t} exista

? f(u,v)= 0 v?V

Proprietatea de conservare a fluxului cere ca fluxul total care pleaca dintr-un varf diferit de sursa si de destinatie sa fie egal cu 0. Plecand de la antisimetrie, se poate rescrie proprietatea de conservare a fluxului ca

? f(u,v) u?V

pentru orice v?V – {s,t}. Adica, in fiecare varf fluxul total este egal cu 0.

Se observa ca fluxul intre varfurile u si v care nu sunt legate prin nici un arc este egal cu 0. Daca (u,v)?E si (v,u)?E atunci c(u,v) =c(v,u)=0, iar din cauza restrictiei de capacitate exista f(u,v)?0 si f(v,u)?0. Dar, deoarece f(u,v)= - f(v,u ) din cauza antisimetriei, rezulta ca f(u,v)= f(v,u)=0.

În concluzie, existenta fluxului nenul intre varfurile u si v implica (u,v)?E sau (v,u)?E sau ambele.

Cantitatea f(u,v) care poate fi pozitiva sau negativa se numeste fluxul net de la varful u la varful v sau pur si simplu fluxul pe arcul(u,v).

Valoarea fluxului f se defineste ca fluxul total care pleaca din sursa:

?f?=? f(s,v) v?V (1)

in care cu ?f? se noteaza valoarea fluxului si nu valoarea absoluta sau cardinalul unei multimi.

Fiind data retea de transport G cu sursa s si destinatia t, problema fluxului maxim cere gasirea unui flux de valoare maxima de la s la t.