Algoritmi In Retele de Transport

1. INTRODUCERE

O ,,rețea de transport” este o rețea (rețele de conducte de fluide, rețele de canale, rețele de străzi etc.) prin care se transportă diverse fluxuri de materiale. De exemplu se consideră un material care este transportat într-un sistem de la sursa unde este produs la destinația unde este consumat. Dacă ceea ce se produce la sursă, este consumat în același ritm la destinație, atunci, în orice punct al sistemului, “fluxul” rețelei reprezintă viteza cu care materialul se deplasează prin rețea. Din punct de vedere informatic, o rețea de transport este un graf orientat caracterizat de unul sau mai multe puncte de intrare în rețea și unul sau mai multe puncte de ieșire din rețea.

Rețelele de transport pot modela curgerea lichidului în sisteme de conducte sau canale, deplasarea pieselor pe benzi rulante, scurgerea curentului prin rețele electrice, deplasarea informațiilor prin rețele de comunicații etc.

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

Vârfurile (nodurile) reprezintă joncțiunile conductelor și în afara vârfurilor sursă și destinație, materialul nu se poate acumula în nici un vârf. Această proprietate se numește,,consevarea fluxului” și este identică cu legea conservării masei care se aplică la bilanțul de materiale sau cu legea lui Kirchoff în cazul curentului electric.

Problema determinării fluxului maxim este cea mai simplă problemă legată de rețelele de transport, care cere să se determine cantitatea maximă de material care poate fi transportată de la sursă la destinație ținând cont de restricțiile de capacitate. Tehnicile de bază ale acestor algoritmi pot fi adaptate la rezolvarea altor tipuri de probleme în rețele de transport.

Pentru rezolvarea problemelor de flux maxim se precizează în continuare următoarele:

formalizarea noțiunilor de rețea de transport și a celei de flux în rețea;

definirea formală a problemei de flux maxim;

metoda clasică Ford-Fulkerson pentru găsirea fluxului maxim;

metoda preflux, care este metoda cea mai rapidă la problemele de flux;

o implementare particulară a algoritmului de preflux.

Rețele de transport și fluxuri

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 nenegativă c(u,v) 0. Dacă (u.v)E se consideră că c(u,v)=0.

Se disting două vârfuri în rețea:

un vîrf sursă s;

un vârf destinație t.

Se presupune că fiecare vârf se găsește pe cel puțin un drum de la sursă la destinație, adică, pentru orice vârf vV există un drum s v t. Graful este deci conex și EV- 1.

Definiția formală a fluxului

Fie G = (V,E) o rețea de transport cu o funcție de capacitate c. Fie s vârful sursă și t vârful destinație. Fluxul în G este o funcție f:VVR cu valori reale care satisface condițiile:

Restricția de capacitate;

Antisimetrie;

Conservarea fluxului.

Restricție de capacitate:Pentru orice u,vV există f(u,v)c(u,v)

Restricția de capacitate impuse ca fluxul de la un vârf la altul să nu depășească valoarea capacității arcului dintre cele două vârfuri.

Antisimetrie: Pentru orice u,vV există f(u,v) = – f(u,v)

Antisimetria impune ca fluxul de la un vârf u la un vârf v să fie egal cu opusul fluxului de la v la u. Astfel, fluxul de la un vârf la el însuși este egal cu 0, deoarece pentru orice uV există f(u,u)= -f(u,u), care implică f(u,u)= 0

Conservarea fluxului: Pentru orice uV – {s,t} există

f(u,v)= 0 vV

Proprietatea de conservare a fluxului cere ca fluxul total care pleacă dintr-un vârf diferit de sursă și de destinație să fie egal cu 0. Plecând de la antisimetrie, se poate rescrie proprietatea de conservare a fluxului ca

f(u,v) uV

pentru orice vV – {s,t}. Adică, în fiecare vârf fluxul total este egal cu 0.

Se observă că fluxul între vârfurile u și v care nu sunt legate prin nici un arc este egal cu 0. Dacă (u,v)E și (v,u)E atunci c(u,v) =c(v,u)=0, iar din cauza restricției de capacitate există f(u,v)0 și f(v,u)0. Dar, deoarece f(u,v)= – f(v,u ) din cauza antisimetriei, rezultă că f(u,v)= f(v,u)=0.

În concluzie, existența fluxului nenul între vârfurile u și v implică (u,v)E sau (v,u)E sau ambele.

Cantitatea f(u,v) care poate fi pozitivă sau negativă se numește fluxul net de la vârful u la vârful v sau pur și simplu fluxul pe arcul(u,v).

Valoarea fluxului f se definește ca fluxul total care pleacă din sursă:

f= f(s,v) vV (1)

în care cu f se notează valoarea fluxului și nu valoarea absolută sau cardinalul unei mulțimi.

Fiind dată rețea de transport G cu sursa s și destinația t, problema fluxului maxim cere găsirea unui flux de valoare maximă de la s la t.

Fluxul pozitiv care intră în vârful v se definește ca:

f(u,v) (2)

uV

f(u,v)0

și fluxul pozitiv care intră într-un vârf trebuie să fie egal cu fluxul pozitiv care iese din vârf (conservarea fluxului)

1.2. Exemplu de rețea de transport

O rețea de transport poate modela problema de transport din figura 1.1. Firma X are o fabrică (sursa s) în orașul Ploiești care fabrică un produs și are un depozit (destinația t) in orașul Satu Mare unde îl stochează. Firma închiriază spațiu în camioane de la o altă firmă pentru a transporta detergentul de la fabrică la depozit. Pentru că spațiul este limitat, firma poate transporta zilnic între oricare două localități u și v numai c(u,v) cutii de produs. Firma X nu poate controla nici rutele de transport și nici capacitățile, deci nu poate modifica rețeaua dată în figura 1.1.

Scopul firmei este de a determina numărul maxim de cutii p care pot fi transportate zilnic la depozit pentru a fabrica exact cantitatea respectivă, deoarece la fabrică nu au spațiu de depozitare. Ritmul cu care se depasează cutiile cu produs de-a lungul rutelor formeaza un flux. Produsul este transmis din fabrică cu un ritm de p cutii/zi și tot p cutii trebuie să ajungă la depozit în fiecare zi. Firma X nu se ocupă de timpul de deplasare a cutiilor în rețea, ci se asigură doar ca p cutii să părăsească fabrica și ca p cutii se ajungă la depozit. Restricția de capacitate impune ca fluxul f(u,v) de la orașul u la orașul v să nu depășească c(u,v) cutii cu produs pe zi. Ritmul cu care ajung cutiile într-un oraș intermediar trebuie să fie identic cu ritmul cu care ele părăsesc orașul respectiv, altfel s-ar îngrămădi. Deci, conservarea fluxului este respectată. Astfel, fluxul maxim în rețea determină numărul maxim p de cutii cu produs transportate zilnic

Fig. 1. Rețeaua de transport a firmei X

În figura următoare, este ilustrat un flux posibil în rețeaua care modelează transportul cutiilor. Pentru oricare două vârfuri u și , fluxul f(u,v) corespunde numărul cutiilor care pot fi transportate într-o zi de la u la v. Dacă f(u,v) este 0 sau negativ, atunci nu există transport de la u la v. În această figură sunt marcate cu două valori (flux/capacitate) doar arcele cu flux pozitiv.

Fig. 2. Flux posibil în rețeaua firmei X

Relația dintre flux și transport se înțelege mai bine dacă se analizează transportul a două vârfuri ca în figura 3 a-e.

Figura 3. arată subgraful indus de vârfurile v1 și v2 din rețeaua de transport din figura 1.

Dacă firma X transportă 8 lăzi pe zi de la v1 la v2 rezultatul este arătat în figura 3.b. Fluxul de la v1 la v2 este de 8 lăzi pe zi. Din cauza antisimetriei se poate spune că fluxul în direcție opusă, adică de la v2 la v1, este de –8 lăzi pe zi, chiar dacă nu se transportă nimic de la v2 la v1.

Fig. 3. Transportul între două vârfuri

În general, fluxul de la v1 la v2 este exprimat prin numărul de lăzi transportate zilnic de la v1 la v2 din care se scade numărul de lăzi transportate de la v2 la v1 . Convenția este de a reprezenta numai fluxuri pozitive, deoarece ele indică un transport real, astfel în figură apare numai valoarea 8, fără valoarea corespunzătoare –8.

Dacă se mai adaugă un transport de 3 lăzi pe zi de la v2 la v1, situația este reprezentată grafic în figura 3.c. Apare acum o situație în care se tranportă în ambele direcții. Se transportă zilnic 8 lăzi de la v1 la v2 și 3 lăzi de la v2 la v1. Fluxul de la v1 la v2 este acum de 8-3=5 lăzi pe zi, iar fluxul de la v2 la v1 este de 3-8 = -5 lăzi.

Situația, datorită rezultatului, este echivalentă cu cea arătată în figura 3.d. De fapt, 3 lăzi pe zi de la v2 la v1 sunt anulate de 3 lăzi din 8 transportate de la v1 la v2 . În ambele situații, fluxul de la v1 la v2 este de 5 lăzi pe zi, dar în figura 3.d. sunt arătate numai transporturile într-o singură direcție.

În general, anulările permit reprezentarea transportului între două vârfuri printr-un flux pozitiv de-a lungul a cel mult unuia dintre cele două arce. Dacă există flux zero sau negativ de la un vârf la altul, nu se face nici un transport în direcția respectivă. Astfel, dacă există transport în ambele direcții între două vârfuri, prin porcesul de anulare, situația poate fi transformată într-una echivalentă în care există transport numai într-o singură direcție: direcția fluxului pozitiv. Restricția de capacitate nu este încălcată în această situație, deoarece fluxul între două vârfuri rămâne același.

În figura 3.e. este arătat efectul transportării a încă 7 lăzi pe zi de la v2 la v1, în care s-a ținut cont de convenția de reprezentare numai a fluxului pozitiv. Fluxul de la v1 la v2 devine 5-7= -2 lăzi , iar fluxul de la v2 la v1 devine 7-5 =2. Deoarece fluxul de la v2 la v1 este pozitiv, el reprezintă un transport de 2 lăzi pe zi de la v2 la v1 . Fluxul de la v1 la v2 este –2 lăzi pe zi și deoarece fluxul nu este pozitiv, nu se realizează nici un transport în această direcție. Altfel spus, se pot considera că 5 lăzi din cele 7 lăzi adiționale pe zi de la v2 la v1 sunt anulate de cele 5 lăzi de la v1 la v2 , ceea ce determină un transport de 2 lăzi pe zi de la v2 la v1 .

1.3. Rețele cu mai multe surse și destinații

O problemă de flux maxim poate avea mai multe surse și mai multe destinații în loc de exact una din fiecare.

De exemplu, firma Y poate avea o mulțime de m fabrici {s1, s2,… sm} și o mulțime de n depozite {t1, t2, …, tn} ca în figura 4.a

Problema găsirii unui flux maxim într-o rețea de transport cu mai multe surse și destinații se poate reduce la problema de flux maxim într-o rețea cu o singură sursă și destinație.

În figura 4.b este ilustrată transformatea rețelei de transport cu mai multe surse si destinații din figura 4.a. într-una cu o singură sursă și o singură destinație. Se adaugă o sursă nouă (supersursă) s și arcele orientate (s. si) cu capacitatea c(s, si)= pentru fiecare i=1,2,…,m. De asemenea, se adaugă o nouă destinație (superdestinație) t și arcele orientate (ti,t) cu capacitatea c(ti, t)= pentru fiecare i=1,2,…,n.

Intuitiv, oricărui flux din rețeaua 4.a. îi corespunde un flux în rețeaua din 4.b. și viceversa. Sursa s produce cantitatea cerută de sursele si, iar destinația t consumă cantitatea cerută de destinațiile ti.

a)

b)

Fig. 4. Transformarea unei rețele de transport cu mai multe surse și destinații într-o rețea cu o singură sursă și o singură destinație

1.4. Însumarea fluxului

Pentru unele funcții (asemănătoare funcției f) care au ca argumente două vârfuri în rețeaua de transport se utilizează a notație de însumare implicită în care oricare din argumentele funcției (chiar amândouă) pot fi mulțimi de vârfuri, cu interpretarea că valoarea respectivă este suma tuturor valorilor funcției pe toate perechile de elemente p de la v2 la v1 devine 7-5 =2. Deoarece fluxul de la v2 la v1 este pozitiv, el reprezintă un transport de 2 lăzi pe zi de la v2 la v1 . Fluxul de la v1 la v2 este –2 lăzi pe zi și deoarece fluxul nu este pozitiv, nu se realizează nici un transport în această direcție. Altfel spus, se pot considera că 5 lăzi din cele 7 lăzi adiționale pe zi de la v2 la v1 sunt anulate de cele 5 lăzi de la v1 la v2 , ceea ce determină un transport de 2 lăzi pe zi de la v2 la v1 .

1.3. Rețele cu mai multe surse și destinații

O problemă de flux maxim poate avea mai multe surse și mai multe destinații în loc de exact una din fiecare.

De exemplu, firma Y poate avea o mulțime de m fabrici {s1, s2,… sm} și o mulțime de n depozite {t1, t2, …, tn} ca în figura 4.a

Problema găsirii unui flux maxim într-o rețea de transport cu mai multe surse și destinații se poate reduce la problema de flux maxim într-o rețea cu o singură sursă și destinație.

În figura 4.b este ilustrată transformatea rețelei de transport cu mai multe surse si destinații din figura 4.a. într-una cu o singură sursă și o singură destinație. Se adaugă o sursă nouă (supersursă) s și arcele orientate (s. si) cu capacitatea c(s, si)= pentru fiecare i=1,2,…,m. De asemenea, se adaugă o nouă destinație (superdestinație) t și arcele orientate (ti,t) cu capacitatea c(ti, t)= pentru fiecare i=1,2,…,n.

Intuitiv, oricărui flux din rețeaua 4.a. îi corespunde un flux în rețeaua din 4.b. și viceversa. Sursa s produce cantitatea cerută de sursele si, iar destinația t consumă cantitatea cerută de destinațiile ti.

a)

b)

Fig. 4. Transformarea unei rețele de transport cu mai multe surse și destinații într-o rețea cu o singură sursă și o singură destinație

1.4. Însumarea fluxului

Pentru unele funcții (asemănătoare funcției f) care au ca argumente două vârfuri în rețeaua de transport se utilizează a notație de însumare implicită în care oricare din argumentele funcției (chiar amândouă) pot fi mulțimi de vârfuri, cu interpretarea că valoarea respectivă este suma tuturor valorilor funcției pe toate perechile de elemente posibile din cele două mulțimi de argumente.

De exemplu, dacă X și Y sunt mulțimi de vârfuri atunci :

f (X,Y)= f(x,y)

xX yY

Astfel, se poate exprima cu ajutorul acestei notații restricția de conservare a fluxului în felul următor: f(u,V)=0 pentru orice uV – {s,t}. Pentru o scriere mai simplă se omit acoladele când mulțimea are un singur element. În formula f(s,V-s)=f(s,V), de exemplu, termenul v-s înseamnă V – {s}. Această notație simplifică formulele în care intervin fluxuri.

În lema următoare sunt cuprinse majoritatea identităților care intervin în probleme de flux și folosesc notația de însumare implicită.

Lema 1. Fie G = (V,E) o rețea de transport și f un flux în G. Atunci:

pentru X V, există f(X,X)=0

pentru X.Y V, există f(X,Y)= – f(Y,X)

pentru X,Z,Y V, cu X Z=0,există f(XY,Z)=f(X,Y)+f(Y,Z) și f(Z,XY)=f(Z,Y)+f(Z,Y)

Ca exemplu de folosire a notației de însumare implicită se demonstrază, în continuare, că valoarea fluxului este egală cu fluxul total care ajunge în vârful destinației, adică:

f=f(V,t) (3)

Intuitiv se observă că această formulă este adevărată. Toate vârfurile diferite de sursă și de destinație au un flux 0 prin conservarea fluxului și astfel vârful destinație este singurul care poate avea un flux diferit de 0 pentru a echivala fluxul diferit de 0 al sursei. O demonstrație formală este următoarea:

Fie o rețea de transport G= (V,E) și fie f1 și f2 două funcții definite în V x V cu valori în R.

Fluxul sumă f1 + f2 este funcția din V x V în R definită prin:

(f1 + f2) = f1(u,v) + f2(u,v) (4)

2. METODA FORD-FULKERSON

Metoda lui Ford – Fulkerson pentru rezolvarea problemei de flux maxim este considerată o metodă (și nu un algoritm) pentru că ea cuprinde mai multe implementări cu diferiți timpi de execuție. Aceasta se bazează pe trei concepte importante, care depășesc cadrul metodei și sunt utilizate și în multe alte probleme legate de fluxuri:

rețele reziduale;

drumuri de ameliorare;

tăieturi.

Metoda lui Ford – Fulkerson este iterativă.

Fie un flux f(u,v) = 0 pentru orice u,vV, ca un flux inițial de valoare 0. La fiecare pas al iterației se va mări valoarea fluxului prin găsirea unui ,,drum de ameliorare”, care este un drum de-a lungul căruia se poate mări fluxul, deci și valoarea lui. Pașii se repetă până când nu se mai găsește nici un drum de ameliorare.

METODA FORD-FULKERSON

fie f fluxul identic cu 0

cât timp există un drum p de ameliorare execută

mărește fluxul f de-a lungul drumului p

returnează f

2.1. Rețele reziduale

Dacă se dă o rețea de transport și un flux, se poate spune intuitiv că rețeaua reziduală constă din arcele care admit flux mai mare. Mai formal, se presupune că există o rețea de transport G = (V,U) cu sursa s și destinația t.

Fie f un flux în G și se consideră o pereche de vârfuri u,vV. Cantitatea de flux adițional care poate fi transportat de la u la v, fără a depăși capacitatea c(u,v), este capacitatea reziduală a arcului(u,v) definită prin:

cf (u,v)= c(u,v) – f(u,v) (5)

De exemplu, dacă c(u,v)= 16 și f(u,v)= 11 se pot transporta în plus cf(u,v)=5 unități de produs fără a depăși capacitatea dată a arcului (u,v). Dacă fluxul f(u,v) este negativ, capacitatea reziduală cf(u,v) este mai mare decât capacitatea c(u,v).

De exemplu, dacă c(u,v)= 16 și f(u,v)= – 4, atunci capacitatea reziduală cf(u,v) = 20 (Există un flux de 4 unități de la v la u, care poate fi anulat prin 4 unități de flux de la u la v. Se pot transporta , apoi, alte 16 unități de la u la v fără a încălca restricția de capacitate pe arcul (u,v). Deci s-au transportat 20 de unități, pornind de la un flux f(u,v)= – 4, fără a depăși capacitatea arcului).

Fiind dată o rețea de transport G= (V,E) și un flux f, rețeaua reziduală a lui G indus de f este Gf = (V, Ef) unde:

Ef = {(u,v)VV : cf(u,v)>0}

Fig. 5.a Rețea de transport

În fig.5.a este reluată rețeaua G și fluxul f din figura 2., pentru care se trasează rețeaua reziduală (fig. 5.b).

Fig. 5.b. Rețea reziduală

În figura 5.b. este prezentată rețeaua reziduală Gf. Fiecare arc al rețelei reziduale sau arc rezidual admite o creștere de flux strict pozitiv. Se observă că (u,v) poate fi arc rezidual în Ef chiar dacă el nu este arc în E ( în concluzie se poate întâmpla ca Ef E).

Rețeaua reziduală din figura de mai sus include arce de acest fel care nu apar în rețeaua inițială, cum ar fi de exemplu arcele (v1,s) și (v2, v3). Un astfel de arc poate să apară în Gf numai dacă (u,v)E și există flux pozitiv de la u la v. Deoarece fluxul f(u,v) de la u la v este negativ , cf(u,v)= c(u,v) – f(u,v) este pozitiv și (u,v) Ef. Deoarece arcul (u,v) poate să apară în rețeaua reziduală numai dacă cel puțin unul din arce (u,v) și (v,u) apar în rețeaua originală, atunci EfE.

Se observă că rețeaua reziduală Gf este o rețea de transport cu funcția de capacitate cf.

Lema 2. Fie G = (V,E) o rețea cu vârful sursă s, respectiv cu vârful destinație t și fie f un flux în G. Fie Gf rețeaua reziduală indusă de fluxul f și fie f ’un flux în Gf.

Atunci fluxul sumă f + f ‘ este un flux în G cu valoarea

f + f ‘=f + f ‘

Această lemă arată legătura dintr-un flux din rețeaua reziduală și fluxul din rețeaua originală.

Demonstrație: Se verifică că antisimetria, restricția de capacitate și proprietatea de conservare sunt verificate:

1. Pentru antisimetrie se observă că pentru orice u,vV există:

(f +f ‘ )(u,v) = f (u,v) + f ‘(u,v) =

= – f (v,u) – f ‘ (v,u) = – (f(v,u) + f ‘ (v,u)) = – (f +f ‘ )(v,u)

2. Pentru restricția de capacitate se observă că f ‘(u.v) cf (u.v) pentru orice u,vV și ținând cont și de formula (5) există:

(f +f ‘ )(u,v) = f (u,v) + f ‘(u,v) f(u,v)+ (c(u.v) – f(u,v))= c(u,v)

3. Pentru proprietatea de conservare se observă că pentru orice

uV – {s,t} există:

(f +f ‘ )(u,v) = f (u,v) + f ‘(u,v) = f (u,v) + f ‘(u,v) = 0 + 0 =0

vV vV vV vV

În final se observă că:

f + f ‘= (f +f ‘ )(s,v) = f (s,v) + f ‘(s,v) = f (s,v) + f ‘(s,v)=f + f ‘

vV vV vV vV

2.2. Drumuri de ameliorare

Fie G = (V,E) o rețea de transport și f un flux în G. Un drum de ameliorare p este un drum simplu de la s la t în rețeaua reziduală Gf.

După definiția rețelei reziduale, fiecare arc (u,v) pe un drum de ameliorare admite un flux pozitiv adițional, fără să încalce restricția de capacitate.

În figura 5.b. drumul trasat colorat este un drum de ameliorare.

Tratând rețeaua reziduală Gf din figură ca o rețea de transport, se pot transporta 4 unități de flux adițional pe fiecare arc de-a lungul acestui drum de ameliorare, fără a încălca restricția de capacitate, pentru că cea mai mică capacitate reziduală pe acest drum este cf (v2,v3)= 4.

Se numește capacitate reziduală a lui p cantitatea maximă a fluxului care poate transporta de-a lungul drumului de ameliorare p.

Capacitate reziduală este dată de formula:

cf(p) = min {cf(u.v): (u,v) este pe drumul p}

Lema următoare, fundamentează cele prezentete mai sus.

Lema 3. Fie G = (V,E) o rețea de transport , f un flux în G și p un drum de ameliorare în Gf. Se definește funcția fp:V V R prin:

Atunci fp este un flux în gf cu valoarea fp=cf(p) > 0

Corolarul următor arată că dacă se adună fp la f se obține un alt flux în G a cărui valoare este mai aproape de valoarea maximă.

În figura următoare (fig. 5.c.) este prezentat rezultatul adunării lui fp din figura 5.b. la fluxul f din figura 5.a.

Fig. 5.c. Adunarea a două fluxuri

Corolar 4. Fie G = (V,E) o rețea de transport , f un flux în G și p un drum de ameliorare în Gf. Fie funcția fp definită ca în formula (1.6). Se definește funcția

f ‘ : V V R, f ‘ = f + fp

2.3. Tăieturi în rețele de transport

Metoda lui Ford – Fulkerson mărește fluxul în mod repetat de-a lungul drumurilor de ameliorare până când se ajunge la un flux maxim.

Teorema de flux maxim – tăietură minimă exprimă faptul că un flux este maxim dacă și numai dacă în rețeaua lui reziduală nu există nici un drum de ameliorare. Pentru a demonstra această teoremă se prezintă noțiunea de tăietură.

O tăietură (S,T) a unei rețele de transport G = (V,E) este o partiție a mulțimii V în mulțimile S și T= V – S astfel încât s S și t T.

Dacă f este un flux, atunci fluxul tăieturii (S,T) este definit ca fiind egal cu f(S,T).

Capacitatea tăieturii (S,T) este c(S,T).

Tăietura minimă este acea tăietură care are cea mai mică capacitate dintre toate tăieturile rețelei

În figura 6. este prezentată tăietura ({s,v1,v2},{v3, v4, t}) corespunzătoare rețelei de transport din figura 5.b.

Fig. 6. Tăietură într-o rețea de transport

Fluxul din această tăietură este:

f(v1, v3) + f(v2, v3) + f(v2, v4) = 12 + (- 4) + 11 = 19

iar capacitatea ei este :

c(v1, v3) + c(v2, v4)= 12 + 14 = 26

Se observă că fluxul unei tăieturi poate avea și fluxuri negative între vârfuri, dar capacitatea unei tăieturi este compusă numai din valori nenegative.

Lema 5. Fie f un flux într-o rețea de transport G cu vârful sursă s și cu vârful destinație t și fie (S,T) o tăietură în G. Atunci fluxul prin tăietura (S,T) este f(S,T)=f

Demonstrație: Din lema 1 rezultă:

f(S,T) = f(S, V) – f (S,S) = f (S,V) = f (s,V) + f (S-s, V) = f (s, V)= f

În această lemă se arată că valoarea unui flux într-o rețea este egală cu fluxul oricărei tăieturi.

Un corolar imediat al lemei 5. este rezultatul demonstrat prin formula 3 și anume că valoarea fluxului este fluxul în vârful sursă.

O altă consecință a lemei 5, care este prezentată în corolarul următor, arată cum se poate folosi capacitatea tăieturii pentru mărginirea valorii fluxului.

Corolarul 6. Valoarea oricărui flux f într-o rețea G este mărginită superior de capacitatea oricărei tăieturi în G.

Demonstrație: Fie (S,T) o tăietură în G și f un flux oarecare in G. Pe baza lemei 5 și folosind restricția de capacitate , se observă:

f = f(S,T) = f(u,v) c(u,v) = c(S,T)

uS vT uS vT

Teorema 7 – Teorema de flux maxim- tăietură minimă.

Dacă f este un flux în rețeaua G = (V,E) cu vârful sursă s și vârful destinație t, atunci următoarele condiții sunt echivalente:

f este un flux maxim în G.

Rețeaua reziduală Gf nu conține nici un drum de ameliorare.

Există o tăietură (S,T) în G pentru care f= c(S,T)

Demonstrație:

(1) (2): Se presupune prin absurd că f este un flux maxim în G și totuși Gf are un drum p de ameliorare.

Conform corolarului 4 suma f +fp, unde fp este dat de formula (6) și este un flux în G cu valoare strict mai mare decâtf, contrazicând presupunerea că este un flux maxim

(2) (3): Se presupune că Gf nu are nici un drum de ameliorare, adică în Gf nu există drum de la s la t. Se definesc mulțimile S și T în felul următor:

S = {v V: există drum de la s la v în Gf }

T = V – S

Partiția (S, T) este o tăietură, în care evident s S și tS, pentru că nu există drum de la s la t în Gf. Pentru orice pereche de vârfuri u și v astfel încât uS și v T, există f(u,v) = c(u,v), deoarece altfel ar exista (u.v)Ef și deci vS.

Conform lemei 5 se observă atunci că f= f(S,T) = c(S,T)

(3) (1): Din corolarul 6 există f c(S,T) pentru orice tăietură (S,T). Condiția

f= c(S,T) implică atunci că f este un flux maxim.

Relația dintre flux și transport se înțelege mai bine dacă se analizează transportul a două tăieturi.

2.4. Algoritmul de bază Ford-Fulkerson

În fiecare iterație a metodei lui Ford-Fulkerson se cauta un drum oarecare de ameliorare p și se mărește fluxul f de-a lungul drumului p cu capacitatea reziduală cf(p). Următoarea implementare a metodei calculează fluxul maxim, în graful G = (V, E), actualizând fluxul f [u,v] între oricare două vârfuri care sunt legate printr-un arc (Se folosesc paranteze drepte când este vorba de o variabilă în program, a cărei valoare se modifică, și paranteze rotunde când este vorba de o funcție).

Dacă u și v nu sunt legate printr-un arc în nici o direcție se presupune că

f [u,v] = 0.

Se presupune că valoarea capacității între vârfurile u și v este dată de funcția c(u,v) calculabilă în timp constant și că c(u,v)= 0 dacă (u,v)E.

Într-o implementare obișnuită valorile c(u,v) sunt păstrate în câmpurile unei liste de adiacență. Capacitatea reziduală se calculează conform formulei (5). În descrierea algoritmului, cf(p) este variabila care păstrează capacitatea reziduală a drumului p.

FORD-FULKERSON(G,s,t)

pentru fiecare arc (u,v)E(G) execută

f [u,v] 0

f [v,u] 0

cât timp există un drum p de la s la t în rețeaua reziduală Gf execută

cf(p) min {cf (u,v): (u,v) este pe drumul p}

pentru fiecare arc (u,v) din p execută

f [u,v] f [u,v] + cf(p)

f [v,u] – f [v,u]

Acest algoritm FORD-FULKERSON reprezintă o tratare extinsă a pseudocodului descris anterior la METODA- FORD-FULKERSON.

În figurile 7.a – 7.e. sunt ilustrate rezultatul fiecărei iterații la o execuție a algoritmului. Liniile 1-3 inițializează fluxul f cu valoarea 0. Ciclul cât timp din liniile 4-8 găsește pe rând câte un drum de ameliorare p în Gf și mărește fluxul f de-a lungul lui p cu valoarea capacității reziduale cf(p). Când nu mai există drum de ameliorare atunci f este un flux maxim.

Fig. 7.a. Rețea de transport cu precizarea capacităților

Fig. 7.b. Rețeaua anterioară la care s-a mărit fluxul cu 4

(arcul (V4, t) s-a saturat)

Fig. 7.c. Fluxul s-a mărit cu 7. Arcul (v4, v3) s-a saturat

Fig. 7.d. Fluxul s-a marit cu 5

Fig. 7.e. Fluxul s-a mărit cu 4. Arcul (v1, v3) s-a saturat. Fluxul maxim este 23 (ce intră = ce iese)

2.5. Analiza algoritmului Ford-Fulkerson

Timpul de execuție a algoritmului FORD-FULKERSON depinde de modul de determinare (în linia a 4) a drumului de ameliorare p . Dacă drumul este ales într-un mod nepotrivit, se poate întâmpla ca algoritmul să nu se oprească: valoarea fluxului crește succesiv, dar nu converge către valoarea maximă. Dacă însă drumul de ameliorare se alege folosind un algoritm de căutare în lățime atunci timpul de execuție a algoritmului este polinomial. Înainte de a demonstra acest lucru se dă o margine superioară în cazul în care drumul este ales arbitrar și toate capacitățile sunt întregi.

În practică problemele de flux maxim apar de obicei cu capacități care sunt numere întregi. Dacă capacitățile sunt numere raționale, cu o scalare potrivită, ele pot fi transformate în numere întregi.

Cu această presupunere, o implementare directă a algoritmului FORD-FULKERSON are un timp de execuție O(Ef*), unde f* este fluxul maxim obținut de algoritm. Timpul de execuție al liniilor 1-3 este (E). Ciclul cât timp din liniile 4-8 este executat de cel multf* ori, deoarece valoarea fluxului crește la fiecare pas cu cel puțin o unitate.

Ciclul cât timp poate fi executat dacă structura de date folosită la implementerea rețelei G=(V,E) se gestionează eficient.

Dacă presupunem că se păstrează o structură de date corespunzătoare unui graf orientat

G ‘ = (V, E ’ ), unde E ‘ = {(u,v): (u,v) E sau (v,u)E}. Arcele din G sunt și arce în G ‘, deci este ușor să se gestioneze capacitățile și fluxurile într-o astfel de structură.

Dându-se un flux f în G, arcele în rețeaua reziduală Gf constau din toate arcele (u,v) din G’ pentru care c(u,v)-f(u,v)0.

Timpul de găsire a unui drum în rețeaua reziduală este deci O(E’)= O(E), indiferent dacă se folosește o căutare in adâncime sau în lățime. Fiecare iterație a ciclului cât timp se execută în O(E) unități de timp, timpul total de execuție a algoritmului FORD-FULKERSON este deci O(Ef*).

Când capacitățile sunt numere întregi și valoare optimală f*a fluxului este mică, timpul de execuție a algoritmului FORD-FULKERSON este bun.

În figura 8 este prezentat cazul în care valoarea fluxului maxim este mare chiar într-o rețea simplă.

Fig. 8. Rețea de transport pentru care algoritmul Ford-Fulkerson are timpul de execuție

În figura de mai sus fluxul maxim este de 2.000.000. Pe drumul s u t sunt transportate 1.000.000 de unități, iar pe drumul s v t sunt transportate alte 1.000.000 de unități.

Dacă primul drum de ameliorare ales de algoritmul FORD-FULKERSON este drumul s u v t, cum se arată în figura 8.a, valoarea fluxului după prima iterație este 1. Rețeaua reziduală corespunzătoare este dată de figura 1.8.b. Dacă în iterația a 2-a drumul de ameliorare ales este cel s v u t, așa cum se arată în figura 8.b atunci valoarea fluxului va fi 2.

În figura 8.c. se arată rețeaua reziduală rezultată. În continuare se pot alege alternativ drumurile s u v t respectiv s v u t. Sunt astfel 2.000.000 de iterații, fluxul crescând la fiecare pas cu câte o unitate. Problema se poate rezolva în numai două iterații, dacă se aleg drumurile s u t și s u t.

Perfomanța algoritmului FORD-FULKERSON poate fi îmbunătățită dacă se implamentează căutarea drumului de ameliorare p printr-o căutare în lățime, adică dacă drumul de ameliorare conține cele mai puține arce de la s la t (cel mai scurt drum, se consideră că fiecare arc are ponderea 1). Această implementare a metodei lui Ford- Fulkerson ca fiind algoritmul lui Edmons-Karp.

În continuare se va demonstra că timpul de execuție al algoritmului lui Edmonds- Karp este O(VE2).

Analiza algoritmului depinde de distanța dintre vârfuri în rețeaua reziduală Gf.

Se notează cu f (u,v) cea mai scurtă distanță de la vârful u la vârful v în Gf, unde fiecare arc are ponderea 1.

Lema 8 Dacă algoritmul lui Edmonds-Karp se folosește pentru o rețea de transport G = (V, E) care are sursa s și destinația t, atunci pentru orice vârf vV – {s,t} distanța f (s.v) în rețeaua reziduală Gf crește monoton cu fiecare ameliorare.

Demonstrație: Se presupune prin absurd că pentru unele vârfuri vV – {s,t} există mărire de flux pentru care f (s,v) descrește. Fie f fluxul înainte de mărire și f ’ după mărire . Atunci, conform presupunerii, se observă:

f ‘ (s,v) < f (s, v)

Se poate presupune, fără a pierde din generalitate, că f ‘ (s, v) f ‘ (s, u) pentru orice vârf uV – {s,t} pentru care f ‘ (s,u) < f (u, v) . Adică, se poate spune că:

f ‘ (s, u) < f ‘ (s, v) implică f (s,u) f ‘ (s, u) (7)

Se consideră un drum de lungime minimă p‘în Gf de forma s u v, unde u precede vârful v. Trebuie să existe relația f ‘ (s, u) = f ‘ (s, v)-1, deoarece (u,v) este un arc pe drumul p’, care este un drum de lungime minimă de la u la v . Dar atunci din (7) rezultă:

f (s,u) f ‘ (s, u)

Cu aceste vârfuri u și v se consideră fluxul f de la u la v înainte de mărirea fluxului în Gf.

Dacă f[u,v]< c(u,v) atunci f (u, v) f (s,u) +1

f ‘ (s, u) +1 = f ‘ (s, v)

ceea ce contrazice presupunerea că mărirea fluxului descrește cu distanța de la s la v .

Deci rezultă că f[u,v] = c(u,v), ceea ce înseamnă că (u,v) Ef. Atunci drumul de ameliorare p , ales în Gf pentru a produce Gf’ trebuie să conțină arcul (u,v) orientat de la v la u, deoarece (u,v)Ef (din ipoteză) și tocmai s-a demonstrat că (u,v) Ef. Deci, pe drumul de ameliorare p se transportă un flux înapoi pe arcul (u,v) și v apare înaintea lui u pe drumul p. Deoarece p este un drum de lungime minimă de la s la t , toate subdrumurile lui sunt de lungime minimă și deci înseamnă că f (s,u)= f (s,v) +1.

În concluzie:

f (s,v) =f (s,u) –1 f ‘ (s, u) –1 = f ‘ (s, v) –2 < f ‘ (s, v)

ceea ce contrazice ipoteza inițială.

Teorema 9 Dacă algoritmul lui Edmonds- Karp este aplicat pentru o rețea de transport G = (V, E) care are sursa s și destinația t, atunci fluxul se mareste de cel mult O(V,E) ori.

Această teoremă dă o margine superioară pentru numărul de iterații în algoritmul lui Edmonds- Karp .

Demonstrație: Se spune că un arc (u,v) în rețeaua reziduală Gf este un arc critic pe drumul de ameliorare p dacă capacitatea reziduală a drumului p este egală cu capacitatea reziduală a arcului(u,v), adică cf(u,v). După mărirea fluxului de-a lungul drumului de ameliorare toate arcele critice dispar din rețeaua reziduală. Mai mult, pe oricare drum de ameliorare trebuie să existe cel puțin un arc critic.

Fie u și v două vârfuri în V legate printr-un arc din E. Trebuie să se știe de câte ori poate fi critic acest arc (u,v) în timpul execuției algoritmului lui Edmonds- Karp.

Pentru că drumul de ameliorare este un drum de lungime minimă, când arcul (u,v) este critic prima dată, există egalitatea:

f (s,v) = f (s,u) + 1

O dată ce fluxul este mărit, arcul (u,v) dispare din rețeaua reziduală. Acesta un poate să reapară pe un alt drum de ameliorare decât dacă fluxul de pe arcul (u,v) descrește, ceea ce se poate întâmpla numai dacă (v,u) apare pe un drum de ameliorare. Dacă f ‘ este fluxul în G, atunci în acest caz:

f ‘ (s, u) = f ‘ (s, v) + 1

Deoareca f (s,v) f ‘ (s, v) conform lemei 1.8 rezultă:

f ‘ (s, u) = f ‘ (s, v) + 1 f (s, v) + 1 = f (s, u) + 2

În consecință, din momentul în care arcul (u,v) devine critic până în momentul când a doua oară devine critic, distanța lui u de la vârful sursă crește cu cel puțin 2. Inițial, distanța lui u de la sursă este cel puțin 0 și în momentul când nu mai poate fi atins din sursă (dacă acest lucru se întâmplă vreodată) distanța lui va fi cel multV – 2, deci, arcul (u,v) poate deveni critic cel mult O(V) ori. Deoarece există O(E) perechi de vârfuri care pot fi legate prin arce în graful rezidual, numărul total de arce critice în timpul execuției algoritmului lui Edmonds- Karp este O(VE). Penru că fiecare drum de ameliorare are cel puțin un arc critic, teorema este demonstrată.

Deoarece la fiecare iterație în algoritmul FORD –FULKERSON poate fi implementată în O(E) unități de timp, când drumul de ameliorare este găsit prin căutare în lățime, timpul total de execuție al algoritmului lui Edmonds- Karp este O(VE2).

În capitolul 3 al lucrării va fi prezentată o metodă cu timpul de execiție O(V2E), care va fi baza algoritmului din capitolul 4 cu timpul de execuție O(V3).

3. ALGORITMI DE PREFLUX

Cei mai rapizi algoritmi de flux maxim până la ora actuală sunt algoritmii de preflux, cu ajutorul cărora se pot rezolva eficient și alte probleme de flux, cum ar fi problema fluxului de cost minim.

În acest capitol se introduce algoritmul ,,generic” de flux maxim al lui Goldberg, care are o implementare simplă ce se execută într-un timp O(V2E), îmbunătățind astfel limita de O(VE2) al algoritmului lui Edmonds- Karp. În capitolul 4 se rafinează algoritmul generic pentru a obține un alt algoritm de preflux cu timp de execuție O(V3).

Algoritmii de preflux lucrează într-o manieră mai localizată decât metoda Ford-Fulkerson. În loc să examineze întreaga rețea rezultată G = (V,E) pentru a determina debitul mărit, algoritmii de preflux acționează asupra unui singur varf la un moment dat, examinând doar vecinii vârfului din rețeaua rezultată. Mai mult, spre deosebire de metoda Ford-Fulkerson, algoritmii de preflux nu păstrează proprietatea de conservare a fluxului de-a lungul execuției lor.

Totuși, acești algoritmi gestionează un preflux, care este o funcție f:V V R care satisface simetria oblică, constângerile de capacitate și următoarea relaxare a conservării fluxului: f(V,u) 0 pentru toate vârfurile u V – {s}. Această semnifică faptul că fluxul net în oricare vârf diferit de sursă este nenegativ.

Se numește exces de flux în u fluxul net în vârful u dat de :

e(u) = f(V,u) (8)

Se spune că un vârf u V – {s, t} este cu exces de flux dacă e(u)>0.

În acest capitol este descrisă intuitiv metoda de preflux, se prelucrează apoi cele două operații implicate în această metodă și anume pomparea prefluxului și ridicarea unui vârf, apoi va fi prezentat algoritmul generic de preflux, iar în final va fi analizată corectitudinea și timpul său de execuție.

3. 1. Aspecte intuitive

Intuiția din spatele metodei de preflux este, cu siguranță, mai bine înțeleasă în termenii fluxurilor de fluide.

Se consideră o rețea de transport G = (V,E) ca fiind un sistem de țevi interconectate de capacități date. Aplicând această analogie metodei Ford – Fulkerson, se poate spune că fiecare drum mărit în rețea produce o debit adițional de fluid, fără puncte de ramificare, care curge de la sursă spre destinație. Metoda Ford – Fulkerson adaugă iterativ mai multe debite de flux până când nu se mai pot adăuga alte debite de fluid.

Algoritmul generic de preflux are o intuiție oarecum diferită. Ca și înainte, arcele orientate corespund unor țevi. Vârfurile, care corespund unor îmbinări de țevi, au două proprietăți interesante:

pentru a gestiona excesul de flux fiecare vârf are o țeavă de scurgere într-un rezervor arbitarar suficient de mare care poate înmagazina fluid;

fiecare vârf, rezervorul corespunzător și toate îmbinările sale cu alte țevi se află pe o platformă a cărei înălțime crește proporțional cu execuția algoritmului.

Înălțimile vârfurilor determină modul în care este pompat fluxul: se pompează doar fluxul de sus in jos, adică, de la un vârf mai înalt spre un vârf mai jos. Poate exista un flux net pozitiv de la un vârf mai jos spre un vârf mai sus, dar operațiile care pompează fluxul vor împinge doar de sus în jos. Înălțimea sursei este fixată la V, iar înălțimea destinației este 0. Toate celelalte înălțimi ale vârfurilor sunt inițial 0 și cresc în timp. La început, algoritmul trimite cât mai mult flux posibil de la sursă la destinație. Cantitatea trimisă este exact cea necesară pentru a umple fiecare țeavă care pleacă de la sursă la întreaga capacitate, de fapt, trimite capacitatea tăieturii (s,V – s). În momentul în care fluxul intră pentru prima dată într-un vârf intermediar, el este colectat în rezervorul vârfului. De acolo este, eventual, pompat în jos.

Este posbil ca singurele țevi care pleacă din vârful u și nu sunt încă saturate cu flux să fie conectate cu vârfuri situate pe același nivel ca și u sau pe un nivel mai sus decât u. În acest caz, pentru a goli vârful u de excesul de flux, trebuie să-i mărim înălțimea – operație numită ridicarea vârfului u. Înălțimea sa este mărită cu o unitate față de înălțimea celui mai jos vârf dintre vecinii săi, cu care este conectat printr-o țeavă nesaturată. Prin urmare, după ce un vârf a fost ridicat, există cel puțin o țeavă de ieșire prin care poate fi pompat mai mult flux.

În final, toate fluxurile care au putut trece prin destinație au ajuns la ea. Nu mai pot ajunge alte fluxuri, pentru că țevile satisfac constrângerile de capacitate, cantitatea de flux de-a lungul oricărei tăieturi este în continuare limitată la capacitatea tăieturii. Pentru a transforma prefluxul într-un flux valid, algoritmul trimite apoi excesul colectat în rezervoarele vârfurilor cu exces de flux înapoi la sursă, continuând să ridice vârfurile deasupra înălțimii fixate Va sursei. Transportul excesului înapoi la sursă este realizat, de fapt, prin anularea fluxurilor care au generat excesul. În momentul în care toate rezervoarele au fost golite, prefluxul nu numai că este un flux valid, el este în același timp și un flux maxim.

3.2. Operații de bază

Există două operații de bază care se execută într-un algoritm de preflux:

pomparea excesului de flux dintr-un vârf către unul din vecinii săi

ridicarea unui vârf.

Aplicabilitatea acestor operații depinde de înălțimile vărfurilor, care vor fi definite formal.

Fie G = (V,E) o rețea de transport cu sursa s și destinația t și fie f un preflux în G. O funcție h:V N este o funcție de înălțime dacă h(s) =V , h(t) = 0. și h(u) h(v) +1 pentru fiecare muchie rezultată (u,v) Ef. Se obține următoarea lemă:

Lema 10. Fie G = (V,E) o rețea de transport, fie f un preflux în G și fie h o funcție de înălțime pe V. Pentru oricare două vârfuri u,v V, dacă h(u) > h(v)+1, atunci (u,v) nu este o muchie în graful rezultat.

Operația de bază POMPEAZĂ(u,v) poate fi aplicată dacă u este un vârf cu exces de flux, cf(u,v)>0 și h(u) = h(v) +1. Pseudocodul următor actualizează prefluxul f într-o rețea G= (V,E). Se presupune că sunt date capacitățile printr-o funcție c constantă în timp și că fiind date c și f, capacitățile rezultate se pot calcula în timp constant. Excesul de flux stocat în vârful u este gestionat de e[u], iar înălțimea lui u este dată de h[u].

Expresia df (u,v) este o variabilă temporară care memorează cantitatea de flux care poate fi pompată de la u la v.

POMPEAZĂ(u,v)

Precondiții: u este excedentar, cf [u,v]>0 și h [u]= h [v] + 1

Acțiune: pompează df (u,v)= min (e [u], cf (u,v) ) unități de flux de la u la v.

df (u,v) min (e [u], cf (u,v) )

f [u,v] f [u,v] + df (u,v)

f [v,u] – f [u,v]

e [u] e [u] – df (u,v)

e [v] e [v] + df (u,v)

Algoritmul POMPEAZĂ operează în felul următor: se presupune că vârful u are un exces pozitiv e [u] și capacitatea rezultată a lui (u,v) este pozitivă.

Astfel, se poate transporta până la df (u,v)= min (e [u], cf (u,v) ) unități de flux de la u la v fără a cauza o valoare negativă pentru e [u] și fără a depăși valoarea pentru capacitatea c(u,v).

Această valoare este calculată în linia 3. Fluxul este mutat de la u la v , actualizând valoarea lui f în liniile 4-5 și valoarea lui e în liniile 6-7. Prin urmare, dacă f este un preflux înaintea apelului procedurii POMPEAZĂ, va rămâne un preflux și după aceea.

Codul algoritmului POMPEAZĂ nu depinde în nici un moment de înălțimile lui u și v, dar se interzice apelul ei dacă condiția h [u]= h [v] + 1 nu este satisfăcută. Astfel, excesul de flux este pompat de sus in jos cu o diferență de înălțime egală cu 1. Conform lemei 10 nu există muchii rezultate între două vârfuri cu diferență între înălțimi mai mare decât 1, deci nu se obține nici un beneficiu permitând fluxului să fie pompat de sus în jos la o diferență mai mare decât 1.

Operația POMPEAZĂ(u,v) se va numi pompare de la u la v. Dacă o operație de pompare este aplicată unei muchii (u,v) care pleacă dintr-un vârf u, se poate spune că și operația de pompare este aplicată lui u. O pompare saturată este cea prin care muchia (u,v) devine saturată (în continuare cf(u,v) = 0), altfel este o pompare nesaturată. Dacă o muchie nu este saturată nu va apărea în rețeaua rezultată.

Operația de bază RIDICĂ(u) se aplică dacă u are exces de flux (este excedentar) și dacă cf(u,v)>0 implică h [u] h [v] pentru toate vârfurile v. Cu alte cuvinte, se poate ridica un vârf excedentar dacă pentru fiecare vârf v pentru care există o capacitate rezultată de la u la v, fluxul nu poate fi pompat de la u la v, deoarece v este situat mai jos decât u. Se ține cont, că pe baza definiției, sursa s și destinația t nu pot fi excedentare , deci s și t nu pot fi ridicate.

RIDICĂ(u)

Precondiții: u este excedentar și pentru orice v V, (u,v) Ef implică h [u] h [v]

Acțiune: mărește înălțimea lui u

h [u] 1 + min { h [v] : (u,v) Ef }

Când se apelează operația RIDICĂ(u), se spune că vârful u este ridicat. Este mai împortant să se menționeze atunci când u este ridicat, Ef trebuie să conțină cel puțin o muchie care iese din u, astfel ca minimul calculat în codul procedurii să corespundă unei mulțimi nevide. Această observație este dedusă din precondiția ca u să fie excedentar. Deoarece e [u] >0, se observă că e [u] = f [v,u] >0, deci trebuie să existe cel puțin un vârf v astfel încât f [v,u] > 0.

Dar atunci cf(u,v) = c(u,v) – f [u,v] = c(u,v) + f [v,u] >0 ceea ce implică (u,v) Ef. Astfel, operația RIDICĂ(u) îi atribuie lui u cea mai mare înălțime permisă de constrângerile funcțiilor de înălțime.

3. 3. Algoritmul generic

Algoritmul generic de preflux folosește următoarea subrutină pentru a crea prefluxul inițial într-o rețea de transport.

INIȚIALIZEAZĂ –PREFLUX (G, s)

pentru fiecare vârf uV[G] execută

h [u] 0

e [u] 0

pentru fiecare muchie (u,v)E[G] execută

f [u,v] 0

f [v,u] 0

h [s] V[G]

pentru fiecare vârf u Adj[s] execută

f [s,u] c(s,u)

f [u,s] – c(s,u)

e [u] c(s,u)

INIȚIALIZEAZĂ –PREFLUX creează un preflux inițial f definit de:

Aceasta înseamnă că fiecare muchie care pleacă din vârful sursă este umplut la întreaga capacitate și toate celelalte muchii nu transportă flux. Pentru fiecare vărf adiacent sursei există inițial e [v] = c(s,v). De asemenea, algoritmul generic începe cu o funcție de înălțime inițială dată de:

Aceasta este o funcție de înălțime pentru că singurele muchii (u,v) pentru care h [u] > h [v] +1 sunt cele pentru care u = s și aceste muchii sunt saturate, ceea ce înseamnă că nu vor fi în rețeaua rezultată

Următorul algoritm tipizează metodele de preflux.

PREFLUX – GENERIC (G)

INIȚIALIZEAZĂ –PREFLUX (G, s)

cât timp există o operație de pompare sau de ridicare se poate aplica execută

selectează o operație de pompare sau de ridicare ce se poate aplica și execut-o

După inițializarea fluxului, algoritmul generic aplică repetat, în orice ordine, operațiile de bază ori de câte ori acest lucru este posibil. Următoarea lemă precizează faptul că atât timp cât există un vârf cu exces de flux, se poate aplica cel puțin una din cele două operații de bază.

Lema 11. – Un vârf excedentar poate fi pompat sau ridicat – Fie G = (V,E) o rețea de transport cu sursa s și destinația t, fie f un preflux în G și fie h o funcție arbitrară de înălțime pentru f. Dacă u este un vârf excedentar oarecare, atunci i se poate aplica fie o operație de pompare, fie o operație de ridicare.

Demonstrație: Pentru orice muchie rezultată (u,v) există h(u) h(v) +1 deoarece h este o funcție de înălțime. Dacă lui u nu i se poate aplica fie o operație de pompare atunci pentru toate muchiile rezultate (u,v) trebuie să existe h(u) < h(v)+1, ceea ce implică h(u) h(v) . Prin urmare lui u i se poate aplica o operație de ridicare.

3.4. Corectitudinea metodei de preflux

Studierea algoritmului de preflux care rezolvă problema fluxului maxim se face analizând :

dacă se termină;

cum se termină;

funcția de înălțime h.

Lema 12 – Înălțimile nu scad niciodată – În timpul execuției algoritmului PREFLUX – GENERIC asupra unei rețele de transport G = (V,E), înățimile h[u], pentru fiecare vârf u V, nu scad niciodată. Mai mult, ori de câte ori se aplică o operație de ridicare asupra unui vârf u , înălțimea sa h[u] crește cu cel puțin 1.

Demonstrație : Deoarece înălțimile vârfurilor se modifică doar în timpul operațiilor de ridicare, este suficient să se demonstreze a doua afirmație a lemei. Dacă vârful este ridicat, atunci pentru toate vârfurile v astfel încât (u,v) Ef, există h[u] h[v].

Aceasta implică h[u] < 1 + min { h[v]: (u,v) Ef } , deci operația trebuie să mărească h[u].

Lema 13 Fie G = (V,E) o rețea de transport cu sursa s și destinația t. În timpul execuției algoritmului PREFLUX – GENERIC asupra unei rețele de transport G = (V,E), atributul h este gestionat ca o funcție de înălțime.

Demonstrație : Demonstrația se face prin inducție după numărul de operații de bază executate.

Dacă h este o funcție de înălțime, atunci operația RIDICĂ(u) să păstreze h ca funcție de înălțime. Dacă se studiază muchia rezultată (u,v) Ef care pleacă din u, atunci operația RIDICĂ(u) asigură că h[u] h[v] +1 după aplicarea ei.

Dacă se studiază muchia rezultată (w,u) care intră în vârful u, conform lemei 12, h[w] h[u] +1 înaintea aplicării operației RIDICĂ(u) , implică h[w] < h[u] +1 după aplicarea ei. Deci operația RIDICĂ(u) păstrează h ca funcție de înălțime.

Se consideră în continuare operația POMPEAZĂ(u,v).

Această operație poate:

adăuga muchia (v,u) la Ef deci h[v] = h[u] – 1 și astfel h rămâne o funcție de înălțime;

poate elimina muchia (v,u) din Ef ceea ce conduce la eliminarea constrângerilor corespunzătoare și , din nou, h rămâne o funcție de înălțime.

Lema 14 Fie G = (V,E) o rețea de transport cu sursa s și destinația t, fie f un preflux în G și fie h o funcție arbitrară de înălțime pe V. Atunci nu există nici un drum de la sursa s la destinația t în rețeaua rezultată Gf.

Demonstrație: Se folosește metoda reducerii la absurd.

Se presupune că există un drum p = (v0, v1, …, vk) de la sursa s la destinația t în Gf unde v0 = s și vk = t. Fără a pierde din generalitate, se presupune că p este un drum elementar, deci k<V. Pentru i = 0,1, …, k-1, muchia (vi, vi+1) Ef.

Deoarece h este o funcție de înălțime, există h(vi) h( vi+1)+1, pentru i = 0,1, …, k-1.

Prin combinarea acestor inegalități de-a lungul drumului p se obține h(s) h(t)+k. Dar pentru că există h(t)= 0, atunci h(s) k <V, ceea ce contrazice cerința ca h(s)=Vpentru o funcție de înălțime.

În continuare se arată că algoritmul generic de preflux se termină si prefluxul pe care îl calculează este un flux maxim.

Teorema 15- Corectitudinea algoritmului generic de preflux-

Dacă execuția algoritmului PREFLUX – GENERIC (G) se termină, pentru o rețea de transport G= (V,E) cu sursa s și destinația t, atunci prefluxul f calculat este un flux maxim pentru G.

Demonstrație: Dacă algoritmul generic de preflux se termină, atunci fiecare vârf din V – {s,t} trebuie să aibe un exces nul, datorită lemelor 11 și 13 și invariantului că f este tot timpul un preflux, deci nu există vârfuri excedentare. Prin urmare f este un flux și h este o funcție de înălțime, conform lemei 14, nu există nici un drum de la s la t în rețeaua rezultată Gf . Conform teoremei flux maxim-tăietură minimă, rezultă că f este un flux maxim.

3.5. Analiza metodei de preflux

Pentru a arăta că algoritmul PREFLUX – GENERIC (G) se termină se stabilește o limită pentru numărul de operații pe care le execută.

Fiecare din cele trei tipuri de operații:ridicare, pompare saturată, pompare nesaturată, este mărginită separat.

Cunoscându-se aceste limite , este ușor să se construiască un algoritm care se execută într-un timp O(V2E). Înaintea începerii analizei este demonstrată următoarea lemă.

Lema 16 Fie G = (V,E) o rețea de transport cu sursa s și destinația t, fie f un preflux în G . Atunci, pentru orice vârf excedentar u, există un drum elementar de la u la s în rețeaua rezultată Gf.

Demonstrație: Se folosește metoda reducerii la absurd.

Fie U = { v : există un drum elementar de la u la v în Gf } și se presupune că s U.

Fie W = V –U.

Se presupune că pentru fiecare pereche de vârfuri v U și w W există f (w,v) 0. Dacă f(w,v)>0 , atunci f(v,w)<0 , ceea ce implică cf(v,w) = c(v,w) – f (v,w)>0. Prin urmare există o muchie (v,w) Ef și un drum elementar de forma u v w în Gf, ceea ce contrazice presupunerea făcută relativ la w. Astfel trebuie să fie f (W,U) 0, deoarece fiecare termen din această sumă este nepozitiv. În concluzie din formula (8) și lema 1, se poate deduce că:

e (U) = f(V,U) = F(W,U) + f(U,U) = f (W,U) 0

Excesele sunt nenegative pentru toate vârfurile din V –{s}. Deoarece s-a presupus că U V –{s}, trebuie ca e(u) =0 pentru toate vârfurile vU . În particular, e(u) =0 , ceea ce contrazice presupunerea că este excedentar.

În următoarea lemă se mărginește înălțimea vârfurilor și corolarul ei stabilește o margine pentru numărul total de operații de ridicare care sunt executate.

Lema 17 Fie G = (V,E) o rețea de transport cu sursa s și destinația t. În orice moment, în timpul execuției algoritmului PREFLUX – GENERIC asupra lui G , există h[u] 2 V-1 pentru toate vârfurile vU .

Demonstrație: Înălțimile sursei s și destinației t nu se modifică niciodată deoarece aceste vârfuri sunt prin definiție neexcedentare.

Deci întotdeauna vor fi adevărate relațiile h[s] = Vși h[t] =0.

Datorită faptului că un vârf este ridicat doar atunci când este excedentar, se poate considera orice vârf excedentar u V –{s}. Conform lemei 1.16, există un drum elementar p de la u la s în Gf.

Fie p = (v0, v1, …, vk) , unde v0 = u și vk= s și k V-1, deoarece p este elementar.

Există (vi, vi+1) Ef. pentru i = 0,1, …, k-1 și , prin urmare, conform lemei 13 h[vi] h[ vi+1]+1. Dezvoltându-se aceste inegalități peste drumul p se obține:

h[u] = h[v0] h[ vk]+k . h[s] + (V-1) = 2V-1.

Corolarul 18: – Limita pentru operații de ridicare-

Fie G = (V,E) o rețea de transport cu sursa s și destinația t. Atunci în timpul execuției algoritmului PREFLUX – GENERIC asupra lui G, numărul de operații de ridicare este cel mult 2V-1 pentru un vârf și cel mult (2V-1) (2V-2) < 2V2 în total.

Demonstrație: Doar vârfurile V –{s,t}, în număr de V-2 pot fi ridicate. Fie u V –{s,t}. Operația RIDICĂ(u) mărește h [u]. Valoarea lui h [u] este inițial 0 și conform lemei 1.17 crește cel mult până la 2V-1. Deci fiecare vârf u V –{s,t} este ridicat de cel mult 2V-1 ori și numărul total de operații de ridicare executate este cel mult (2V-1) (2V-2) < 2V2 .

Lema 17 se utilizează pentru mărginirea pompărilor saturate.

Lema 19 – limita pentru pompări saturate-

În timpul execuției algoritmului PREFLUX – GENERIC asupra oricărei rețele de transport G= (V,E), numărul de pompări saturate este cel mult 2VE .

Demonstrație: Pentru orice pereche de vârfuri u,v V, se iau în considerare pompările saturate de la u la v și de la v la u. Dacă astfel de pompări există, cel puțin una dintre (u,v) și (v,u) este o muchie în E. Se presupune că a apărut o pompare saturată de la u la v. Pentru ca să fie posibil să apară o altă o pompare saturată de la u la v, algoritmul trebuie mai întâi să pompeze fluxul de la u la v, ceea ce nu este posibil decât după ce h[v] crește cu cel puțin 2. Asemănător h[u] trebuie să crească cu cel puțin 2 între două pompări saturate de la u la v.

Se consideră secvența A de numere întregi date de h[u] + h[v] pentru fiecare pompare saturată care apare între vârfurile u și v.

Se dorește să se mărginească lungimea acestei secvențe. Când apare prima pompare în oricare dintre direcții între vârfurile u și v. , trebuie să existe h[u] + h[v] 1 și astfel primul întreg din A este cel puțin 1. Când apare ultima astfel de pompare, atunci h[u] + h[v] (2V -1) + (2V- 2) = 4V-3, conform lemei 17. Astfel, ultimul întreg din A este cel mult 4V-3. În A pot apărea cel mult toți ceilalți întregi.

În concluzie, numărul de întregi din A este cel mult:

( (4V-3) –1)/2+1 = 2V-1.

Se adaugă 1 pentru a fi siguri că ambele capete ale secvenței sunt numărate.

Numărul total de pompări saturate de la u la v este de cel mult:

2V-1.

Înmulțind cu numărul total de muchii, se obține că numărul total de pompări saturate poate fi cel mult (2V-1)E< 2VE.

În următoarea lemă se stabilește o margine pentru numărul de pompări nesaturate din algoritmul generic de preflux.

Lema 20 – limita pentru pompări nesaturate – În timpul execuției algoritmului PREFLUX – GENERIC asupra oricărei rețele de transport G= (V,E), numărul de pompări nesaturate este cel mult 4V2(V+E).

Demonstrație: Se definește o funcție de potențial = h[v] , unde XV

vX

este o mulțime de vârfuri excedentare. Inițial = 0. Se observă că ridicarea unui vârf u mărește cu cel mult 2V, deoarece mulțimea peste care se face însumarea este aceeași și u nu poate fi ridicat mai mult decât înălțimea sa maximă posibilă, care conform lamei 17 este cel mult 2V. De asemenea, o pompare saturată de la vârful u la vârful v mărește cu cel mult 2V, deoarece înălțimile nu se modifică și doar vârful v, a cărui înălțime este cel mult 2V, poate, eventual, deveni excedentar.. Se observă că o pompare nesaturată de la u la v micșorează cu cel puțin 1, deoarece u nu mai este excedentar după pompare, v devine excedentar după pompare chiar dacă nu era înaintea operației, iar h[v] – h[u] = -1.

În concluzie, pe parcursul algoritmului, numărul total de creșteri în este constrâns de corolarul 18 și lema 19, la valoarea

(2V)( 2V2) + (2V)( 2VE)= 4V2(V +E)

Deoarece 0, rezultă că numărul total de descreșteri și deci numărul total de pompări nesaturate este cel mult 4V2(V+E).

Teorema 21 În timpul execuției algoritmului PREFLUX – GENERIC asupra oricărei rețele de transport G= (V,E), numărul de operații de bază este O(V2E) .

Demonstrație: Pe baza corolarului 18 și a lemelor 19 și 20 demonstrația este imediată.

Corolarul 22 Există o implementare a algoritmului generic de preflux care se execută într-un timp O(V2E) pentru orice rețea de transport G= (V,E).

4. ALGORITMUL MUTARE-ÎN-FAȚĂ

Metoda prefluxului permite aplicarea operațiilor de bază în absolut orice ordine. Problema fluxului maxim se poate rezolva totuși mai repede decât marginea O(V2E) dată de corolarul 22 prin alegerea atentă a ordinii și administrarea eficientă a structurii de date corespunzătoare rețelei.

Algoritmul mutare –în- față este un algoritm de preflux de complexitate temporară O(V3) , este asimptotic cel puțin la fel de bun ca și O(V2E).

Algoritmul mutare –în- față gestionează o listă a vârfurilor rețelei. Algoritmul parcurge lista începând din față, selectând repetat un vârf u la care apare o depășire și apoi ,,descărcându-l”, adică realitând operațiile de pompare și ridicare până când u nu mai are un exces pozitiv. Indiferent care vârf este ridicat, el este mutat în capul listei (se mută în față) după care algoritmul reia parcurgerea listei.

Corectitudinea și analiza algoritmului mutare –în- față depind de noțiunea de muchii ,,admisibile”, adică acele muchii din rețeaua reziduală prin care poate fi pompat fluxul. După demonstrarea unor proprietăți despre rețeaua muchiilor admisibile, se va investiga operația de descărcare și apoi va fi prezentat algoritmul mutare –în- față.

4.1. Muchii și rețele admisibile

Dacă G = (V,E) este o rețea de transport cu sursa s și destinația t, f este un preflux în G, iar h este funcția de înălțime , atunci muchia (u,v) este o muchie admisibilă dacă cf(u,v)>0 și h (u) = h(v) +1. În caz contrar (u,v) este inadmisibilă.

Rețeaua admisibilă este Gf,h = (V,Ef,h ), unde Ef,h este mulțimea muchiilor admisibile.

Rețeaua admisibilă constă din acele muchii prin care poate fi pompat fluxul.

În următoarea lemă se demonstrează că rețeaua admisibilă este un graf orientat aciclic.

Lema 23 – Rețeaua admisibilă este aciclică – Dacă G = (V,E) este o rețea de transport cu sursa s și destinația t, f este un preflux în G și h este funcția de înălțime pe G, atunci rețeaua admisibilă Gf,h = (V,Ef,h ) este aciclică.

Demonstrație: Se folosește metoda reducerii la absurd.

Se presupune că Gf,h conține un ciclu p = (v0, v1, …, vk) , unde v0 = vk și k>0. Întrucât fiecare muchie din p este admisibilă, atunci h(vi -1)= h(vi) + 1 pentru i = 1,2,…,k.

Însumând de-a lungul ciclului obținem:

k k k

h(vi -1)= (h(vi) + 1) = h(vi) + k

i=1 i=1 i=1

Deoarece fiecare vârf din ciclul p apare o dată în fiecare sumă, rezultă că 0=k, ceea ce constituie o contradicție.

Lema 24 Fie G = (V,E) o rețea de transport cu sursa s și destinația t, fie f un preflux în G și fie h o funcție de înălțime. Dacă la un vârf u apare depășire și (u,v) este o muchie admisibilă, atunci aplică problema POMPEAZĂ (u,v). Operația nu produce nici o muchie admisibilă nouă, dar se poate transforma muchia (u,v) într-una inadmisibilă.

Demonstrație: Prin definiția unei muchii admisibile rezultă că fluxul poate fi pompat de la u la v. Întrucât u este de depășire, se aplică operația POMPEAZĂ (u,v). Singura muchie reziduală nouă care poate fi creată prin pomparea fluxului de la u la v este muchia (u,v). Întrucât h(v) = h(u) – 1, muchia (u,v) nu poate deveni admisibilă. Dacă operația este de pompare saturată, atunci cf (u,v) = 0 după care (u,v) devine inadmisibilă.

Lema 25 Fie G = (V,E) o rețea de transport cu sursa s și destinația t, fie f un preflux în G și fie h o funcție de înălțime. Dacă un vârf u este de depășire și nu există muchii admisibile care pleacă din u, atunci se aplică RIDICĂ(u). După operație de ridicare există cel puțin o muchie admisibilă care pleacă din u, dar nici o muchie admisibilă ce intră în v.

Demonstrație: Dacă u este de depășire, conform lemei 11 i se aplică o operație fie de pompare fie de ridicare. Dacă nu există muchii admisibile care pleacă din u, nu poate fi pompat nici un flux dinspre u și se aplică operația RIDICĂ(u).

După operație de ridicare există h[u] = 1+ min { h[v]:(u,v ) Ef}. Astfel, dacă v este un vârf care realizează minimul în această mulțime, muchia (u,v) devine admisibilă. Deci, după ridicare există cel puțin o muchie admisibilă care pleacă din u.

Pentru a arăta că nici o muchie admisibilă nu intră în u după o operație de ridicare, se presupune că există un vârf v, astfel încât (v, u) să fie admisibilă. Atunci după ridicare h[v] = h[u] +1 și deci h[v] > h[u] +1 imediat înaintea ridicării. Dar lema1.10 rezultă că nu există nici o muchie reziduală între vârfuri a căror înălține diferă cu mai mult de 1.Mai mult, ridicarea unui vârf nu schimbă rețeaua reziduală. Astfel, (u,v) nu este rețeaua reziduală și deci nu poate fi în reteaua admisibilă.

4.2. Liste de adiacență

Muchiile dintr-un algoritm mutare-în-față sunt organizate în ,,liste de adiacență”.

Fiind dată o rețea de transport G = (V,E) cu sursa s și destinația t, lista de adiacență N[u] pentru vârful u V este o listă sumplu înlănțuită a vâdfurilor adiacente lui u în G. Astfel, vârful v apare în lista N[u] dacă (u,v)V sau dacă (v,u ) E.

Lista de adiacență N[u] conține exact acele vârfuri pentru care poate exista o muchie reziduală (u,v). Primul vârf din N[u] este indicat de cap[N[u]]. Vârful care urmează lui v în lista de adiacență este indicat de urm_adiacent[v]. Acest pointer N[u]este NIL dacă v este ultimul vârf în lista de adiacență.

Algoritmul mutare-în-față ciclează prin fiecare listă de adiacență într-o ordine arbitrară fixată de execuția algoritmului. Pentru fiecare vârf u, câmpul actual[u] indică ârful curent luat în considerare din N[u]. La început actual[u] este inițializat cu cap[N[u]].

Descărcarea unui vârf de depășire

Un vârf de depășire este descărcat prin pomparea întregului exces de flux prin muchiile admisibile spre vârfurile adiacente, ridicând u cât este necesar pentru a obține ca muchiile ce pleacă din u să fie admisibile. Pseudocodul este prezentat în continuare:

DESCARCĂ(u)

căt timp e [u] > 0 execută

v actual[u]

dacă v = NIL atunci

RIDICĂ (u)

actual[u] cap[N[u]]

altfel

dacă cf (u,v)>0 și h[u] = h[v] +1 atunci

POMPEAZĂ(u,v)

altfel

actual[u] urm_adiacent[v]

În figurile următoare (figurile 9 a-g) este prezentată parcurgerea câtorva iterații ale ciclului cât timp din liniile 1-10 care se execută cât timp vârful u are un exces pozitiv:

Fig. 9.a. Descărcarea unui vârf

Sunt necesare 15 iterații ale ciclului CÂT TIMP din procedura DESCARCA pentru a pompa tot excesul de flux din vârful y. Doar vecinii lui y și muchiile care intră în y sunt desenate. În fiecare componentă, numărul din interiorul fiecărui vârf este excesul său de la începutul fiecărei iterații desenate în componenta respectivă și fiecare vârf este desenat la înălțimea componentei sale.

La dreapta este lista de adiacență N[y] la începutul fiecărei iterații, cu numărul iterației în sus.

Fig. 9.b.

După ridicare vârful y are înălțimea 1. În iterațiile 5, 6 muchiile (y,s) și (y,x) sunt găsite a fi inadmisibile dar 8 unități de flux în exces sunt pompate din y în z în iterația 7. Din cauza pompării actual[y] nu este avansat în această iterație.

Fig. 9.c.

Deoarece pomparea din iterația 7 a saturat muchia (y, z) ea este găsită inadmisibilă în iterația 8. În iterația 9 actual[y]=NIL și astfel vârful y este din nou ridicat, iar actual[y] este resetat

Fig. 9.d.

În iterația 10, muchia (y,s) este inadmisibilă, iar în iterația 11 sunt pompate 5 unități de flux în exces din vârful y în vârful x.

Fig. 9.e.

Deoarece actual[y] nu a fost avansat în iterația 11, iterația 2 găsește muchia (y,x) ca inadmisibilă. Iterația 13 găsește muchia (y,z) inadmisibilă, iar iterația 14 ridică vârful y și resetează valoarea lui actual[y].

Fig. 9.f.

Iterația 15 împinge 6 unități de flux în exces din y în s.

Fig. 9.g.

Vârful y nu mai are exces de flux și iterația se încheie. Acest exemplu începe și se termină cu pointerul curent la capătul listei de adiacență, dar în general nu este cazul.

Fiecare iterație realizează una din cele trei acțiuni, depintând de vârful actual v din lista de adiacență N[u].

Dacă v este NIL, atunci s-a trecut de ultimul elemente din lista de adiacență N[u]. Linia 4 ridică vârful u și atunci linia 5 resetează vârful adiacent actual al lui u pentru a fi primul din N[u].

Lema care va fi prezentată ulterior, lema 1.26 afirmă că în această situație se aplică operația de ridicare.

Dacă v nu este NIL și (u,v) este o muchie admisibilă (determinată de testul din linia 7), atunci linia 8 pompează o parte (posibil și integral) din excesul lui u spre vârful v.

Este de remarcat faptul că dacă algoritmul DESCARCĂ(u) este apelat pentru un vârf de depășire u, atunci ultima acțiune realizată de DESCARCĂ(u) trebuie să fie o pompare din u. Pentru că porcedura se termină numai când e [u]devine zero și nici operația de ridicare, nici avansarea pointerului actual[u] nu afectează valoarea lui e [u] .

Trebuie ca atunci când POMPEAZĂ sau RIDICĂ sunt apelate de către DESCARCĂ(u) , operațiile se aplică.

Lema 26 – Dacă DESCARCĂ(u) apelează POMPEAZĂ(u,v) în linia 8, atunci o operație de pompare se aplică lui (u,v). Dacă DESCARCĂ(u) apelează RIDICĂ (u) în linia 4, atunci lui u i se aplică o operație de ridicare.

Demonstrație: Testele din liniile 1 și 7 asigură că o operație de pompare apare numai dacă operația se aplică, ceea ce demonstrează prin prima afirmație din lemă.

Pentru a demonstra a doua afirmație, se consideră că testul din linia 1 și lemei 25, este nevoie să arătăm doar că toate muchiile care pleacă din u sunt inadmisibile. Se observă că pe măsură ce DESCARCĂ(u) este apelată repetat, pointerul actual[u] se mișcă în josul listei N [u] .

Fiecare trecere începe de la capul lui N[u] și se termină cu actual[u] = NIL , moment în care u este ridicat și începe o nouă trecere. Pentru ca pointerul actual[u] să avanseze dincolo de un vârf v N[u] în timpul unei treceri, muchia (u,v) trebuie să fie considerată inadmisibilă de către testul din linia 7.

Astfel, în momentul în care trecerea se termină, fiecare muchie plecând din u fost determinată ca fiind inadmisibilă la un moment dat în timpul trecerii. Observația cheie este că la sfârșitul trecerii, fiecare muchie care pleacă din u este încă inadmisibilă pentru că conform lemei 24 a pompării, nu se poate crea nici o muchie admisibilă, lăsând una singură care pleacă din u. Astfel, orice muchie admisibilă trebuie să fie mai întâi creată printr-o operație de ridicare. Din vârful u nu este ridicat în timpul trecerii și din lema 25 nici un alt vârf v care este ridicat în timpul trecerii nu are muchii admisibile care intră în el. Astfel, la sfârșitul fiecărei treceri toate muchiile care pleacă din u rămân inadmisibile, deci lema este demonstrată.

4.3. Algoritmul mutare-în-față

În algoritmul mutare – în- față se gestionează o listă înlănțuită L, formată din toate vârfurile din V –{s,t}.O proprietate cheie este că vârfurile din L sunt sortate topologic conform rețelei admisibile. Conform lemei 23 rețeaua admisibilă este un graf orientat aciclic.

Pseudocodul pentru algoritmul mutare – în- față presupune că listele de adiacență N[u] au fost deja create pentru fiecare vârf u. El presupune că și urm[u] indică spre vârful care urmează lui u în L și că urm[u] =NIL dacă u este ultimul vârf din listă.

MUTĂ-ÎN-FAȚĂ(G,s,t)

INIȚIALIZEAZĂ –PREFLUX (G, s)

L V [G] –{s,t}, în orice ordine

pentru fiecare vârf uV[G] -{s.t} execută

actual[u] cap[N[u]]

u cap[L]

cât timp uNIL execută

vechea_înălțime h[u]

DESCARCĂ (u)

Dacă h[u]> vechea_înălțime atunci

mută u în capul listei L

u urm[u]

Algoritmul mutare –în- față lucrează după cum urmează. Linia 1 inițializează prefluxul și înălțimile la aceleași valori la fec ca și algoritmul generic de preflux. Linia 2 inițializează lista L astfel încât să conțină toate vârfurile potențiale de depășire, în orice ordine. Liniile 3-4 inițializeză pointerul curent al fiecărui vârf u spre primul vârf din lista de adiacență a lui u.

În figura 10.a-e sunt prezentate etapele ciclului cât timp din liniile 6-11 prin parcurgerea listei L și prin descărcarea vârfurilor. Linia 5 asigură că parcurgerea începe cu primul vârf din listă. De fiecare dată de-a lungul ciclului este descărcat un vârf u în linia 8. Dacă u a fost descărcat de către procedura DESCARCĂ, linia 10 îl mută în capul listei L. Această detrminare este făcută prin salvarea înălțimii lui u în variabila vechea_înălțime înainte de operația de descărcare (linia 7) și compararea acestei înălțimi salvate cu înălțimea lui u de după aceea (linia 9). Linia 11 utilizează vârful următor lui u din lista L pentru a face următoarea iterație a ciclului cât timp. Dacă u a fort mutat în capul listei, vârful folosit în următoarea iterație este cel ce urmează lui u în noua sa poziție pe listă.

Fig. 10.a. Acțiunea algoritmului MUTĂ-ÎN-FAȚĂ

În figura de mai sus avem o rețea de transport imediat înainte de prima iterație a ciclului cât timp. Inițial 26 de unități de flux părăsesc sursa s. La dreapta este dată lista inițială, L = (x, y, z) cu u=x. Sub fiecare vârf din lista L este lista sa de adiacență, cu vecinul curent. Vârful x este descărcat. El este ridicat la înălțimea 1, sunt pompate spre y unități de flux, iar cele 7 unități rămase în exces sunt pompate spre destinația t. Deoarece x este ridicat el este mutat în capul lui L, care în cazul acesta nu schimbă structura lui L.

Fig. 10.b.

Următorul vârf care este descărcat este y deoarece el urmează după x în lista L.

Fig. 10.c.

Vârful x urmează acum după y în L și astfel el este din nou descărcat, pompând cele 5 unități de flux în exces spre t. Deoarece vârful x nu este ridicat la acest pas el rămâne pe loc în lista L.

Fig. 10.d.

Vârful z care urmează dupa y în L va fi descărcat. El este ridicat la înălțimea 1 și toate cele 8 unități de flux în exces sunt pompate spre t. Deoarece z a fost ridicat el este mutat în capul listei L.

Fig. 10.e.

Vârful y care urmează după z în lista L este iar descărcat. Deoarece y nu are exces procedura DESCARCA revine imediat și y rămâne pe loc. Urmează vârful x care este descărcat. Deoarece nici el nu are exces procedura DESCARCA revine imediat și x rămâne pe loc în lista L. Algoritmul MUTĂ-ÎN-FAȚĂ a atins sfârșitul listei L și se termină. În acest moment nu mai există vârfuri cu depășire, iar prefluxul este flux maxim.

Pentru a se arăta că MUTĂ-ÎN-FAȚĂ(G,s,t) calculează un flux maxim, se arată că el este o implementare a algoritmului generic de preflux. Mai întâi, se observă că el realizează numai operațiile de pompare și ridicare când ele se aplică, întrucât lema 26 garantează că DESCARCĂ le realizează numai când ele se aplică. Pentru a se arăta că atunci când MUTĂ-ÎN-FAȚĂ(G,s,t) se termină, nu se aplică nici o operație de bază, se observă că dacă u ajunge la sfârșitul lui L, fiecare vărf din L (cu posibila excepție a primului vârf, care poate avea exces) trebuie descărcat fără a produce o ridicare.

În lema următoare, lema 27, se afirmă că lista L este gestionată ca o sortare topologică a rețelei admisibile. Astfel, o operație de pompare are ca efect miscare fluxului în exces spre vârfuri mai în josul listei (sau spre s sau t). Dacă pointerul u ajunge la sfârșitul listei, excesul fiecărui vârf este 0 și nici una din operațiile de bază nu se aplică.

Lema 27 Dacă se execută MUTĂ-ÎN-FAȚĂ(G,s,t) pe o rețea de transport G=(V,E) cu sursa s și destinația t , atunci fiecare iterație a ciclului cât timp din liniile 6-11 menține invariant faptul că L este o sortare topologică a vârfurilor din rețeaua admisibilă Gf,h = (V,Ef,h).

Demonstrație: Imediat după ce INIȚIALIZEAZĂ –PREFLUX (G, s) a fost executat, h[s] =[V] și h[t]= 0 pentru oricare v V –{s}. Deoarece [V] 2 (întrucât el în conține cel puțin pe s și t), nici o muchie nu poate fi admisibilă. Astfel Ef,h și orice ordonare a lui V–{s,t} este o sortare topologică a lui Gf,h.

Se demonstrază în continuare că invariantul este menținut prin fiecare iterație a ciclului cât timp. Rețeaua admisibilă este schimbată numai prin operații de pompare și ridicare. Conform lemei 1.24 operațiile de pompare produc numai muchii inadmisibile. Astfel, muchii admisibile pot fi create numai prin operații de ridicare. După ce un vârf este ridicat, totuși , lema 1.25 afirmă că nu există muchii admisibile care intră în u, dar pot exista muchii admisibile care pleacă din u. Astfel prin deplasatea lui u în capul listei L, algoritmul asigură că orice muchie admisibilă plecând din u satisface ordonarea sortarii topologice.

4.4. Analiza algoritmului

Se demonstrează că timpul de execuție al algoritmului MUTĂ-ÎN-FAȚĂ(G,s,t) este O(V3) pe orice rețea de transport G=(V,E). Întrucât algoritmul este o implementare a algoritmului de preflux, se folosește corolarul 18 care furnizează o margine O(V) pentru numărul de operații de ridicare executate pentru fiecare vârf și o margine O(V2) pentru numărul total de ridicări; o margine O(VE) pentru timpul total consumat cu efectuarea operațiilor de ridicare, iar lema 19 furnizează o margine O(VE) pentru numărul total de operații de pompare saturate.

Teorema 28. Timpul de execuție al algoritmului MUTĂ-ÎN-FAȚĂ(G,s,t) pe orice rețea de transport G=(V,E). este O(V3).

Demonstrație: Se consideră o ,,fază” a algoritmului MUTĂ-ÎN-FAȚĂ ca fiind durata dintre două operații consecutive de ridicare. Există O(V2) faze, deoarece sunt O(V2) operații de ridicare. Fiecare fază constă din cel mult V apelări ale procedurii DESCARCĂ, după cum urmează:

dacă DESCARCĂ nu realizează o operație de ridicare, următorul apel al procedurii DESCARCĂ este mai în josul listei L și lungimea lui L este mai mică decât V;

dacă DESCARCĂ realizează o operație de ridicare, următorul apel al procedurii DESCARCĂ aparține unei faze diferite. Deoarece fiecare fază conține cel mult Vapelări ale lui DESCARCĂ și sunt O(V2) faze, numărul de apelări ale lui DESCARCĂ în linia 8 din din procedura MUTĂ-ÎN-FAȚĂ este O(V3).

Astfel, lucrul total realizat de ciclul cât timp în MUTĂ-ÎN-FAȚĂ, excluzând cel realizat în DESCARCĂ, este cel mult O(V3).

Se evaluează în continuare volumul de calcul realizat de DESCARCĂ în timpul execuției algoritmului. Fiecare iterație a ciclului cât timp din DESCARCĂ realizează una din cele trei acțiuni:

operația de ridicare(liniile 4-5) – margine a timpului O(V,E) pentru toate cele O(V2) ridicări care sunt executate;

actualizarea pointerului actual[u] (linia 8)- această acțiune se produce de O(grad(u)) ori de câte ori un vârf u este ridicat și de O(V .grad(u)) ori global pentru acel vârf. Deci , pentru toate vârfurile, volumul total de calcul necesar pentru avansarea pointerilor în lista de adiacență este O(VE) .

operația de pompare (linia 7) – Se știe că numărul total de operații de pompare saturate este O(VE). Dacă se execută o pompare nesaturată, DESCARCĂ se termină imediat, întrucât pomparea reduce excesul la 0. Astfel, există cel mult o pompare nesaturată pentru fiecare apel al procedurii DESCARCĂ. S-a observat anterior că DESCARCĂ este apelată de O(V3) ori și astfel timpul total consumat realizând pompări nesaturate este O(V3).

Timpul de execuție al algoritmului MUTĂ-ÎN-FAȚĂ(G,s,t) pe orice rețea de transport G=(V,E) deci O(V3 + VE) care este O(V3).

5. APLICAȚIE PENTRU ALGORITMUL „Mutare-în-față”

În acest capitol este descrisă o aplicație realizată în limbajul C pentru calculul fluxului maxim printr-o rețea de transport cu ajutorul algoritmului de preflux.

5.1. Codificarea datelor

Vârfurile rețelei (V(G)\{s,t}) formează lista vârfurilor ce pot fi admisibile (asupra cărora se aplică, operația descarcă() – lista L, din algoritm). Rezultă o listă simplu înlănțuită dată prin capul sau (vlista) și legătura la vârful următor în fiecare vârf (legătura vurm).

Toate arcele rețelei, asociate unui vârf sursa din graf formează lista de adiacență a vârfului respectiv, lista de arce simplu înlanțuită, dată prin capul listei (specifică vârfului, adiacente) și legătura la arcul următor din fiecare arc în parte (aurm).

Legătura la vârful actual în lista de adiacențe (adiacente), asociată unui vârf este prin legătura actual, asociată vârfului.

Rezultă că o rețea poate fi reprezentată sub forma:

n = numărul de vârfuri;

m = numărul de arce;

s = vârful sursă;

t = vârful final;

vlista = listă simplu înlănțuită a vârfurilor ce pot fi ”descărcate” (minus s si t);

varfuri = vectorul tuturor vârfurilor din rețea, dat prin pointer – ul la primul element;

arce = vectorul tuturor arcelor din rețea, dat prin pointer –ul la primul element din vector.

Fiecare arc introdus în rețea, a = (v1,v2), este introdus împreună cu arcul simetric, simetric(a) = (v2,v1), cu, capacitate(a) = capacitatea citită din fișierul de intrare; capacitate(simetric(a))=0.

Tot, așa, reziduul pe fiecare arc este tot una cu capacitatea pe arcul respectiv, inițial, deci, pentru fiecare arc am reprezentat numai reziduul.

Deci, am considerat următoarea codificare pentru vârfurile rețelei:

h = înălțimea vârfului;

e = excesul de flux în vârful respectiv;

vurm = legatura la vârful următor, pentru vârfurile din lista L = V(G) \ {s,t};

adiacente = capul listei de arce adiacente, asociate vârfului;

actual = legătura la arcul actual asociat vârfului în algoritm.

Pentru arcele din lista de adiacente a unui vârf v, codificarea este:

vdest = vârful destinație asociat arcului (v,vdest);

f = fluxul curent, asociat arcului;

r = reziduul (inițial, capacitatea arcului, sau 0, dacă arcul nu există);

aurm = legătura la arcul urmator în lista de adiacente asociată vârfului v;

parc = poziția arcului simetric, codificată pe un bit (0 – dacă arcul simetric urmează după arcul curent, 1 – dacă arcul simetric este înainte de arcul curent în vectorul arce asociat rețelei).

5.2. Rezultate obținute

Interfața programului este prezentată în figura următoare. Rezultatele sunt afișate pe ecran dar sunt și trimise în fișierul de ieșire specificat de utilizator.

Fig. 11. Interfața programului

Un exemplu de rețea pentru care a fost aplicat programul este prezentată în figura următoare.

Fig. 12. Rețea analizată cu programul propus

Observăm că în paranteză sunt trecute valorile fluxului pe fiecare arc pentru fluxul maxim calculat prin rețea.

Deoarece rezultatele sunt preluate dintr-un fișier programul are avantajul ca se pot simula rețele cu dimensiuni mari, eventualele modificări afectând doar fișierul inițial. De asemenea, se pot crea diferite variante ale fișierului de intrare pentru aceeași rețea, precum și ale fișierului de ieșire. Practic nu există restricții impuse pentru cele două fișiere utilizate de program, fiind totuși recomandabil să se lucreze cu perechi de fișiere cu nume sugestive și asemănătoare (de ex. input.txt și output.txt).

ANEXĂ

/*Algoritmul Mutare-în-față */

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <stdarg.h>

#include <stdarg.h>

char nume_input[128]; /* numele fișierului de intrare: */

char nume_output[128]; /* numele fișierului de ieșire: */

/* declarații `forward’ pentru structurile `vârf’ și `arc’: */

struct __varf;

struct __arc;

typedef struct __varf {

int h;

long e;

struct __varf *vurm;

struct __arc *adiacente;

struct __arc *actual;

} varf;

typedef struct __arc {

int vdest;

long r, f;

unsigned parc:1;

struct __arc *aurm;

} arc;

typedef struct {

int n,m;

int s,t;

varf *varfuri,*vlista;

arc *arce;

} retea;

/* eroare(mesaj): afișează în fișierul standard de eroare, `stderr’ un mesaj, după care părăsește aplicația: */

void eroare(const char* mesaj) {

fprintf(stderr,"%s\n",mesaj);

exit(1);

}

/* aloca(len) – alocă dinamic un spațiu de lungime `len’, umplut cu zerouri, prin funcția standard calloc(no_blocuri,len_bloc), din <stdlib.h>; returnează un pointer la spațiul alocat: */

void* zaloca(unsigned len) {

void* p = calloc(1,len);

if(!p) eroare("Memorie insuficienta!");

return p;

}

/* aloca_retea(cn,cm,cs,ct) – alocă dinamic spațiul pentru o structură de tip `retea’ și pentru vectorii `vârfuri’ și `arce’, asociați acesteia, după care o inițializeaza și întoarce adresa structurii; primește ca argumente numărul de vârfuri(n), numărul de arce(m), vârful sursă în rețea(s) și vârful terminus din rețea(t): */

retea* aloca_retea(int cn,int cm,int cs,int ct) {

/* calculează spațiul necesar pentru cele trei elemente structură `rețea’ + vectorul de arce + vectorul de vârfuri:*/

unsigned len = sizeof(arc)*2*cm + sizeof(varf)*cn + sizeof(retea);

/* variabila `pos’ (pointer la un octet) este folosită pentru a calcula deplasamentele celor doi vectori față de începutul spațiului alocat; inițializat cu spațiul alocat: */

char* pos = (char*)zaloca(len);

/* structura rețea `începe’ la prima poziție a spațiului alocat: */

retea* r = (retea*)pos;

pos += sizeof(retea); /*calculează poziția de `dupa’ rețea */

/* urmează vectorul `vârfuri’, al vârfurilor: */

r->varfuri = (varf*)pos;

pos += sizeof(varf)*cn; /* calculează poziția de `dupa’ vectorul de vârfuri:*/

/* urmează vectorul de arce: */

r->arce = (arc*)pos;

/* inițializează ordinul grafului, sursă și final: */

r->n = cn;

r->s = cs;

r->t = ct;

/* retunează rețeaua alocată: */

return r;

}

/* dinaltime(r,acurent) – returnează înalțimea vârfului destinație asociat unui arc dat prin legătura `acurent’, în rețeaua `r’: */

int dinaltime(retea* r,arc* acurent) {

varf* pvd = r->varfuri + acurent->vdest;

return pvd->h;

}

/* ridica(r,vcurent) – efectuază operația de ridicare pentru un vârf dat prin legătura sa `vcurent’ în retțaua `r’: */

void ridica(retea* r, varf* vcurent){

int hmin = r->n*2 + 1, h;

arc *acurent;

/*parcurge lista de arce adiacente asociată legăturii `vcurent’ și calculează h minim pentru toate arcele care au un reziduu pozitiv: */

for( acurent = vcurent->adiacente;acurent;acurent = acurent->aurm)

if( (acurent->r > 0) && ((h = dinaltime(r,acurent)) < hmin) )

hmin = h;

vcurent->h = hmin + 1;

}

/* pompeaza(r,vsursa,acurent) – execută operația de pompare prin arcul dat prin legătura `acurent’, cu vârful sursă dat prin legătura `vsursa’, în rețeaua `r’, reglând reziduul și fluxul pe arcele `acurent’ și arcul simetric și excesul în `vsursa’ și vârful destinație asociate arcului: */

void pompeaza(retea* r, varf* vsursa, arc* acurent) {

varf *pvdest = r->varfuri + acurent->vdest;

arc *asimetric = acurent->parc ? acurent – 1 : acurent + 1;

long delta = vsursa->e < acurent->r ? vsursa->e : acurent->r;

vsursa->e -= delta;

pvdest->e += delta;

acurent->r -= delta;

acurent->f += delta;

asimetric->r += delta;

asimetric->f = -acurent->f;

}

/*descarca(r,vsursa) – execută operația de `descarcare’ (golirea excesului) din vârful dat prin legătura `vsursa’ în rețeaua `r’; */

void descarca(retea* r, varf *vsursa) {

arc *acurent = vsursa->actual;

while(vsursa->e > 0)

if(!acurent) {

ridica(r,vsursa);

acurent = vsursa->adiacente;

}

else if( (acurent->r > 0) &&

(vsursa->h == dinaltime(r,acurent) + 1) )

pompeaza(r,vsursa,acurent);

else acurent = acurent->aurm;

vsursa->actual = acurent;

}

/* initializeaza_preflux(r) – inițializează prefluxul în rețeaua `r’, adică, inițializează excesul în vârsul sursă `s’ cu o valoare foarte mare, după care execută pompările din `s’ către toate celelalte vârfuri, inițializează înălțimile vârfurilor, valorile legăturilor `actual’ pentru fiecare vârf, și lista `vlista’ : */

#define INFINIT 0x7FFFFFFFL

void initializeaza_preflux(retea *r){

int v;

arc *acurent;

varf *vsursa = r->varfuri + r->s;

vsursa->e = INFINIT;

for(acurent = vsursa->adiacente; acurent; acurent = acurent->aurm)

if(acurent->r)

pompeaza(r,vsursa,acurent);

for(v=0, vsursa = r->varfuri;v < r->n; v++, vsursa++) {

if((v!=r->s) && (v!=r->t)) {

vsursa->vurm = r->vlista;

r->vlista = vsursa;

}

vsursa->actual = vsursa->adiacente;

vsursa->h = 1;

}

r->varfuri[r->s].h = r->n;

r->varfuri[r->t].h = 0;

}

/* calculeaza_flux( r ) – calculează fluxul în rețeaua `r’ după algoritmul `mută-în-față’: */

void calculeaza_flux(retea *r) {

varf *vsursa, *vanterior;

int hvechi;

initializeaza_preflux(r);

for(vsursa = r->vlista, vanterior = NULL; vsursa;

vanterior = vsursa, vsursa = vsursa->vurm) {

hvechi = vsursa->h;

descarca(r,vsursa);

if((vsursa->h > hvechi) && vanterior){

vanterior->vurm = vsursa->vurm;

vsursa->vurm = r->vlista;

r->vlista = vsursa;

}

}

}

/* cauta_arc(r,x,y) – caută arcul x->y în lista de adiacente asociată vârfului `x’, în rețeaua `r’ și întoarce legătura la acesta sau NULL, dacă nu l-a găsit: */

arc* cauta_arc(retea* r,int x, int y) {

arc* acurent;

for(acurent = r->varfuri[x].adiacente;acurent;acurent = acurent->aurm)

if( acurent->vdest == y) return acurent;

return NULL;

}

/* insereaza_pereche(r,v1,v2,c,arcnou) – inserează în vectorul de vârfuri `arce’ din rețeaua `r’, o pereche de arce simetrice (v1->v2) și (v2,v1), primul cu capacitatea, `c’, începând cu prima poziție liberă din vectorul `arce’ data prin legătura `arcnou’; întoarce noua poziție liberă din vector (adica, arcnou + 2): */

arc* insereaza_pereche(retea *r,int v1, int v2, long capacitate,arc *arcnou){

varf *pv1 = r->varfuri + v1;

varf *pv2 = r->varfuri + v2;

arcnou->vdest = v2;

arcnou->r = capacitate;

/* arcul (v1->v2) este inserat în lista de adiacente a lui v1: */

arcnou->aurm = pv1->adiacente;

pv1->adiacente = arcnou;

++arcnou;

arcnou->vdest = v1;

arcnou->parc = 1;

/* arcul (v2->v1) este inserat în lista de adiacente a lui v2: */

arcnou->aurm = pv2->adiacente;

pv2->adiacente = arcnou;

++arcnou;

r->m += 2;

return arcnou;

}

/* afiseaza_retea( r ) – afisează rețeaua `r’, citită din intrare, pe ecran: */

void afiseaza_retea(retea* r) {

int v1,v2;

arc *acurent;

printf("Reteaua citita din fisierul %s:\n",nume_input);

printf("n = %d m = %d s = %d t = %d\n",r->n,r->m,r->s+1,r->t+1);

puts("Arce:");

for(v1 = 0;v1 < r->n; v1++) {

printf("L(%d):",v1+1);

for( acurent = (r->varfuri + v1)->adiacente;

acurent; acurent = acurent->aurm)

if(acurent->r > 0)

printf("->%d = %ld ",

acurent->vdest + 1,acurent->r);

puts("");

}

getch();

}

/* citeste_retea(nume_fis) – citește datele de intrare din fișierul de intrare `nume_fis’ într-o structură de tip rețea `r’, pe care o alocă mai întâi, și returnează adresa spațiului alocat pentru `r’; fișierul de intrare conține codificarea:

Prima linie: n m s t

Celalte m linii: v1 v2 capacitate

, adică arce (v1->v2) și capacitatea asociată: */

retea* citeste_retea(const char* nume_fis) {

FILE* in = fopen(nume_fis,"rt");

int v1,v2,k,cn,cm,cs,ct;

long c;

arc *acurent,*arcnou;

retea *r;

if(!in) eroare("Nu pot deschide fisierul de intrare!");

if(fscanf(in,"%d %d %d %d\n",&cn,&cm,&cs,&ct)!=4)

eroare("Nu pot citi din intrare!");

–cs;–ct;

r = aloca_retea(cn,cm,cs,ct);

for(k = 0, arcnou = r->arce; k < cm; k++) {

if(fscanf(in,"%d %d %ld\n",&v1,&v2,&c)!=3)

eroare("Eroare de citire din fisierul de intrare!");

if(v1 == v2)

eroare("Garful retelei nu admite bucle!");

–v1;–v2;

if(acurent = cauta_arc(r,v1,v2)) {

if(acurent->r)

eroare("Arcul a mai fost introdus o data!");

else acurent->r = c;

}

else arcnou = insereaza_pereche(r,v1,v2,c,arcnou);

}

fclose(in);

afiseaza_retea(r);

return r;

}

/* afiseaza_flux(out,r) – scrie fluxul rezultat într-un stream de ieșire – `out’, pentru rețeaua `r’:*/

void afiseaza_flux(FILE* out,retea *r) {

int v,vd;

long fmax = 0;

arc *acurent;

fprintf(out,"s = %d, t = %d\n",r->s + 1,r->t + 1);

for(v = 0; v < r->n;v++)

for(acurent = r->varfuri[v].adiacente;acurent;acurent=acurent->aurm)

if(acurent->f > 0) {

fprintf(out,"f[%d,%d]=%ld\n",

v+1,acurent->vdest +1,acurent->f);

if(ferror(out))

eroare("Eroare de scriere in iesire!");

if( v == r->s ) fmax += acurent->f;

}

fprintf(out,"Flux maxim la intrare:%ld\n",fmax);

if(ferror(out)) eroare("Eroare de scriere la iesire!");

}

/* scrie_retea(nume_fis,r) – scrie fluxul rezultat pe ecran și într-un fișier precizat prin numele său, `nume_fis’, pentru rețeaua `r’: */

void scrie_retea(const char* nume_fis,retea* r) {

FILE* out = fopen(nume_fis,"w+t");

if(!out) eroare("Nu pot deschide fisierul de iesire!");

afiseaza_flux(out,r);

fclose(out);

afiseaza_flux(stdout,r);

getch();

}

/* programul principal devine: */

void main(void) {

retea *r;

clrscr();

puts("Numele fisierului de intrare:");

scanf("%s",nume_input);

puts("Numele fisierului de iesire:");

scanf("%s",nume_output);

r = citeste_retea(nume_input);

calculeaza_flux(r);

scrie_retea(nume_output,r);

free(r);

}

BIBLIOGRAFIE

Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Introducere în algoritmi, Editura Agora, 1999

Cornelius Croitoru, Tehnici de bază în optimizarea combinatorie, Editura Universității ,,Al. I. Cuza” Iași 1992

Ioan Tomescu, Curs de combinatorică și teoria grafurilor, Editura Universității București, 1980

Giumale Cristian, Introducere în analiza algoritmilor, Editura Polirom, Iași, 2005