Problema determinării unui flux maxim

Având dată o reţea de transport să se determine un flux astfel încât fluxul la ieşirea

reţelei să fie maxim.

Algoritmi pentru rezolvarea problemelor de flux într-o reţea de transport au fost

dezvoltaţi de:

Ford, Fulkerson (1956),

Edmonds, Karp (1969),

Dinic (1970), Karzanov (1973),

Cherkassky (1976),

Malhotra şi alţii (1978), Galil (1978),

Galil şi Naamad (1979),

Sleator şi Tarjan (1980),

Goldberg şi Tarjan (1985).

Se da o retea de transport sub forma unui graf orientat cu N noduri si M arce. Fiecare arc

are asociata o capacitate si un cost pentru fiecare unitate de flux ce trece pe arcul

respectiv. Notam cu S si D sursa si respectiv destinatia din reteaua de transport

considerata. Sa se determine costul minim pentru a se transmite o cantitate maxima de

flux de la sursa la destinatie.

Indicatii de rezolvare

Aceasta problema se rezolva in mod asemanator cu problema determinarii fluxului

maxim cu cateva modificari. Este din nou necesara constuirea grafului rezidual, care

contine toate arcele din graful initial si, in plus, toate arcele de intoarcere. Astfel, pentru

fiecare arc x->y de cost z din graful initial se adauga in graful rezidual arcul y->x cu

capacitatea 0 si costul -z. Algoritmul ruleaza atat timp cat se mai poate introduce flux in

retea. La fiecare pas, este necesara gasirea unui drum de ameliorare de cost minim de la

sursa la destinatie. Apoi, fluxul va fi incrementat pe acest drum cu valoarea maxima

posibila (minimul diferentelor dintre capacitate si flux pentru fiecare arc de pe drum).

Pentru a gasi drumul de ameliorare optim din punct de vedere al costului putem folosi un

algoritm de drum minim care sa permita existenta costurilor negative pe arce (costurile

arcelor de intoarcere), precum Bellman-Ford .Algoritmul Bellman-Ford are complexitate

O(N*M), ceea ce conduce la o complexitate teoretica O(N2*M2), insa in practica se

comporta mai bine. Algoritmul Bellman-Ford poate fi rafinat folosind o coada pentru a

mentine nodurile ce mai pot contribui la imbunatatirea costurilor. Desi complexitatea

ramane aceeasi, in practica timpul de rulare scade simtitor.

Pentru a imbunatati algoritmul de mai sus, atunci cand cautam drumul de ameliorare de

cost minim putem folosi si algoritmul lui Dijkstra, dar inainte graful trebuie modificat

astfel incat sa nu mai exista arce cu cost negativ.Algoritmul lui Dijkstra are complexitate

O(M*logN), deci complexitatea totala devine O(N*M2*logN), dar este iarasi

supraestimata.

Aplicatii

Algoritmul de flux maxim si cost minim poate fi aplicat si pentru grafuri neorientate cu

modificari minime. In plus, poate fi aplicat si pentru determinarea cuplajului de cost

minim intr-un graf bipartit. De asemenea, putem determina si cuplajul de cost maxim

intr-un graf biparit, folosind acelasi algoritm dupa ce costul fiecarei muchii a fost inlocuit

cu diferenta dintre valoarea maxima a unei muchii si valoarea curenta. In acest caz,

rezultatul va fi egal cu diferenta dintre produsul fluxului si valoarea maxima a unei

muchii si costul fluxului obtinut pe graful modificat.

Algoritmul Ford-Fulkerson

Algoritmul Ford-Fulkerson constă in identificarea succesivă a unor drumuri de creştere până în momentul în care nu mai există nici un astfel de drum.

După identificarea unui drum de creştere se determină valoarea acestuia, iar aceasta se scade din costurile fiecărui arc (i, j) de pe drumul respectiv şi se adună la costurile arcelor corespunzătoare de forma (j,i). De asemenea, valoarea respectivă se adună la fluxul maxim determinat până în momentul respectiv.

Datorită faptului că un drum de creştere conţine arce care au costuri pozitive, valoarea sa va fi întotdeauna un număr pozitiv. Ca urmare, pentru fiecare drum de creştere determinat, valoarea fluxului va creşte cu cel puţin o unitate. Datorită faptului că avem capacităţi finite, fluxul maxim este un număr finit. Din aceste motive suntem siguri că, mai devreme sau mai târziu, algoritmul se va încheia.

Există două părţi complementare ale algoritmului de maximizare a fluxului între două noduri ale unei reţele:

în pasul 1, se caută un lanţ de flux augmentativ între cele două noduri s şi t; odată găsit, se desfăşoară pasul 2;

în pasul 2, se calculează care este surplusul de flux adus de lanţul găsit şi apoi se fac modificările adecvate în încărcarea arcelor, pentru a asigura flux maxim; se reia pasul 1 al algoritmului pentru a găsi un alt lanţ, i se modifică şi acestuia fluxul, şi aşa mai departe.

Acesta este un proces iterativ, care caută în mod repetat lanţuri şi le modifică fluxul, până când nici un lanţ nu mai este găsit. Când se întâmplă acest lucru, fluxul de la sursă la destinaţie are cea mai mare valoare posibilă; distribuţia fluxurilor în arcele reţelei este una dintre (poate mai multe) posibilele alocări de flux care conduc la maximizarea fluxului total.

Intrând mai în amănunt, când se face căutarea de lanţuri augmentative, nodurile lanţului se etichetează cu o etichetă dublă, astfel: prima valoare indică nodul anterior (pentru arcele directe) sau posterior (pentru arcele inverse) de unde se preia fluxul, iar a doua valoare indică valoarea surplusului de flux ce poate fi trimis de la sursă la nodul curent.

Ar putea fi posibil, odată ce un lanţ a fost găsit, să examinăm fiecare din arcele componente, în ordinea în care surplusul de flux este calculat. Dar este mult mai convenabil să folosim etichete pentru aceasta, iar după ce etichetele au fost stabilite, calculele se realizează cu ajutorul tehnicii recursive. Să presupunem că nodul j a fost etichetat, iar nodul imediat predecesor în lanţ este nodul i, care are deja eticheta (ai, bi). Se disting două cazuri ce trebuie examinate:

dacă este un arc direct (i,j), atunci capacitatea potenţială a surplusului de flux este u(i,j)-x(i,j); capacitatea lanţului de la s la j va fi valoarea minimă dintre:

- capacitatea lanţului de la s la i;- capacitatea potenţială a arcului (i,j).

Deci, eticheta nodului j se defineşte ca (i, min(bi, u(i,j)-x(i,j))).

dacă este un arc invers (j,i), atunci capacitatea potenţială a surplusului de flux este x(j,i); capacitatea lanţului de la s la i va fi valoarea minimă dintre:

- capacitatea lanţului de la s la i;- capacitatea potenţială a arcului (j,i).

Deci, eticheta nodului j se defineşte ca (i, min(bi, x(j,i))).

( Uneori este mai convenabil de recunoscut un arc invers prin marcarea etichetei ai = -i )

Pentru a porni procedura de etichetare, iniţial toate nodurile sunt neetichetate, iar sursei s, din moment ce predecesorul său e inexistent, i se dă eticheta (-, ), deci fluxul de la el către el însuşi poate fi oricât de mare. Apoi nodurile sunt etichetate găsind arce care au un capăt etichetat şi celălalt nu şi care pot fi folosite ca lanţuri augmentative. Dacă lanţul este unul augmentativ, în cele din urmă va fi etichetat prin acest algoritm şi nodul t. Apoi fluxul prin acel lanţ va fi crescut (pentru arcele directe) sau scăzut (pentru arcele inverse) cu valoarea bt, valoare calculată prin modalitatea de mai sus. Algoritmul se repetă până când singurul nod neetichetat rămas este nodul destinaţie, t.

Algoritmul Ford-Fulkerson constă în parcurgerea următoarelor etape:

1. Se iniţializează fluxul cu valoarea 0 pentru toate arcele reţelei:

Uuu ,0

2. Pentru reţeaua de transport se construieşte reţeaua reziduală. 3. Se caută un drum (de-a lungul căruia poate fi mărit fluxul) în reţeaua reziduală

de la intrarea la ieşirea reţelei. a. Dacă nu există nici un astfel de drum algoritmul se opreşte, fluxul găsit

este flux maxim.

b. Altfel se calculează uc min şi se modifică fluxul astfel:

luuu ,

luuu ,

4. Algoritmul se repetă pasul începând cu pasul 2.

Algoritmul poate fi prezentat sub forma unei scheme logice de forma:

Studiu de caz

O reţea de transport G=(V,E) este un graf orientat în care fiecărui arc (u,v) E îi este asociată o capacitate pozitivă c(u,v) ≥0. Dacă (u,v) E vom considera că c(u,v)=0. Vom distinge două vârfuri în reţea: un vârf sursă s şi un vârf destinaţie t.

Fie G=(V,E) o reţea de transport cu o funcţie f:V*V cu valori reale care satisface următoarele trei condiţii:Restricţie de capacitate: Pentru orice u,v V avem f(u,v) ≤ c(u,v).Antisimetrie: Pentru orice u,v V avem f(u,v) = -f(v,u).

Conservarea fluxului: Pentru orice u V-{s,t} avem .

Să ne imaginăm o situaţie în care un material este transportat într-un sistem de la sursă, unde este produs, la destinaţie, unde este consumat. La sursă se produce materialul într-un ritm constant, iar la destianţie se consumă în acelaşi ritm. Intuitiv, „fluxul” materialului, în orice punct al sistemului, este ritmul în care materialul se deplasează. Reţelele de transport pot modela scurgerea lichidului în sisteme cu ţevi, deplasarea pieselor pe benzi rulante, scurgerea curentului prin reţele electrice, deplasarea informaţiilor prin reţelele de comunicaţii, şi multe altele.

Fiecare arc în reţeaua de transport poate fi considerat drept conductă pentru material. Fiecare conductă are o capacitate dată, care este de fapt ritmul maxim cu care lichidul se poate deplasa în conductă. De exemplu, printr-o ţeavă pot curge cel mult 2000 litri pe oră, sau pe un fir conductor cu curent electric de maxim 20 amperi. Vârfurile (nodurile) sunt joncţiunile conductelor şi în afara vârfului sursă şi destinaţie, materialul nu se poate acumula în nici un vârf. Altfel spus, cantitatea de material care intră trebuie sa fie egală cu cea care iese. Această proprietate se numeşte „conservarea fluxului” şi este identică cu legea lui Kirchoff în cazul curentului electric.

Fig. 1: O reţea de transport

s

1

4

3

2

t

5

2

9 10

2

8

4

3

6

5

Exemplul clasic de reţea de transport este reprezentat de o serie de conducte dispuse într-un robinet s şi un canal de scurgere t. Fiecare conducta (i,j) este caracterizata prin cantitatea maximă de apă c(i,j), care poate să treacă la un moment dat prin conductă. Problema aflării fluxului maxim presupune determinarea cantitaăţii maxime de apă care poate fi pompată prin robinetul s astfel încât pe nici o conductă să nu se depăşească capacitatea maximă permisă. În figura 1 este preyentată o reţea de transport cu 7 noduri, dintre care o sursă s şi o destinaţie t. Fiecărui arc îi este ataşată o valoare pozitivă, reprezentând capacitatea maximă admisă pe arcul respectiv.

Pentru a rezolva problema fluxului maxim folosim algoritmul lui Ford Fulkerson optimizat.

Algoritmul constă în 4 paşi:

P1. Iniţializăm fluxul reţelei de transport F 0.P2. Pargurgem graful în lăţime (BF) pentru a găsi un drum în creştere de la s la t cu număr minim de muchii. De exemplu pentru fig. 1 avem:

Drumul gasit fiind: s 1 2 t

P3. În cazul când acesta a fost găsit se actualizează valorile fluxului pe drumul găsit şi se trece la P2. Altfel, se trece la P4.

Valoare fluxului pe drumul găsit reprezintă minimul dintre arcele care îl alcătuiesc.c(s,1)=2; c(1,2)=4; c(2,t)=6, deci fluxul este 2.

În acest caz arcul (s,1) devine 0, deci nu va mai putea fi folosit în următoare parcurgere.După acest pas graful va arăta astfel:

Fig. 2

s

1

4

3

2

t

5

2

9 10

2

8

4

3

6

5

Prima valoare reprezentând valoare fluxului curent pe acel arc, acesa va fi întotdeauna mai mică sau egală cu capacitatea maximă, f(u,v) ≤c(u,v).P4. Se afişează fluxul maxim.

Pentru exemplul dat următorii paşi sunt:

* determinăm un drum în creştere:

* obţinem fluxul maxim 5

Fig. 3

s

1

4

3

2

t

5

2/2

0/9 0/10

0/2

0/8

2/4

0/3

2/6

0/5

Fig. 4

s

1

4

3

2

t

5

2/2

0/9 0/10

0/2

0/8

2/4

0/3

2/6

0/5

* determinăm din nou un drum de la s la t

* de această dată fluxul maxim este 3

* vom parcurge şi acum graful în lăţime (BF: s,4,3), dar de această dată nu găsim un drum de la s la t şi deci în acest caz trecem la pasul P4

* Fluxul maxim se poate obţine prin însumarea fluxurilor obţinute pe parcurs (2+5+3=10)

Fig. 5

s

1

4

3

2

t

5

2/2

5/9 5/10

0/2

5/8

2/4

0/3

2/6

5/5

Fig. 6

s

1

4

3

2

t

5

2/2

5/9 5/10

0/2

5/8

2/4

0/3

2/6

5/5

Fig. 5

s

1

4

3

2

t

5

2/2

8/9 8/10

0/2

8/8

2/4

3/3

5/6

5/5