Fluxuri In Retele. Metoda de Etichetare a Nodurilor Pentru Rezolvarea Problemei de Flux Maxim

Introducere

Una din cele mai importante și interesante probleme care se poate rezolva cu ajutorul grafurilor este aceea de a determina valoarea fluxului maxim care poate fi transmis de la o sursă specificată s a unui graf, la un alt vârf (ieșire) t al grafului. Această problemă și variațiile ei pot fi aplicate într-un număr mare de probleme practice, de exemplu în determinarea fluxului maxim a ratei de trafic între două localități pe un drum reprezentat ca un graf.

O metodă de rezolvare a problemei de flux maxim între s și t a fost realizată de Ford și Fulkerson și metoda lor de „etichetare”. Ford și Fulkerson au fost primii care au studiat problema fluxului maxim, au stabilit un număr de rezultate și au dezvoltat un algoritm pentru aflarea lui. Metoda lor originală nu a fost un algoritm pentru că nu se termină întotdeauna. Edmonds și Karp au modificat această metodă pentru a asigura terminarea procesului. Algoritmul modificat de ei avea complexitatea O(|N||A|2), pentru un graf G=(N,A). Mulți alții au studiat problema fluxului maxim. Dinic a făcut un algoritm de complexitate O(|N|2|A|) și mai târziu Karzanov a îmbunătățit tehnica lui Dinic, algoritmul lui are complexitatea O(|N|3). Între timp, acești algoritmi au fost și mai mult îmbunătățiți cu ajutorul unor tehnici sofisticate de structuri de date.

În literatura de specialitate au fost discutate câteva posibile variații ale problemei de flux maxim de la s la t. Scopul acestei lucrări este să descrie aceste probleme, să arate relațiile dintre ele, și să descrie algoritmii pentru rezolvarea lor.

Capitolul I, „Flux maxim în rețele. Problema de bază” conține noțiunile de bază, anumite notații, enunțul problemei, teorema și algoritmul lui Ford-Fulkerson în cazul capacităților întregi, graful incrementat, teorema de descompunere a fluxului, împreună cu exemple.

Capitolul II, „Variații ale problemei fluxului maxim”, prezintă cazul intrărilor și ieșirilor multiple, fluxuri cu limite inferioare pe arce, fluxuri în rețele nedirecționate și mixte, capacități în noduri.

Capitolul III, „Flux minim în rețele”, prezintă problema fluxului minim, algoritmul lui Ford-Fulkerson și un exemplu.

Capitolul IV, „Fluxul maxim între oricare pereche de vârfuri”, prezintă echivalența fluxului, condensarea vârfurilor, un algoritm pentru determinarea fluxului maxim între toate perechile de vârfuri și un exemplu.

Capitolul V, „Flux de cost minim de la s la t”, prezintă un algoritm bazat pe determinarea ciclurilor negative, un algoritm care crește fluxul pe drumurile de cost minim din graful rezidual, descrierea acestora și exemple.

Capitolul VI , „Fluxuri în grafuri cu câștiguri”, prezintă această problematică, lanțurile de mărire a fluxului, ciclurile active, un algoritm pentru aflarea fluxului optim pentru grafuri cu câștiguri cu exemple, și grafuri cu câștiguri ale vârfurilor.

Capitolul VII, „Aplicații”, prezintă o implementare în limbajul PASCAL a algoritmilor Ford-Fulkerson pentru rezolvarea problemei fluxului maxim și a problemei fluxului minim, împreună cu exemple de rulare.

CAPITOLUL

FLUX MAXIM ÎN REȚELE. PROBLEMA DE BAZĂ.

1.Noțiuni

Se numește rețea directă sau graf linear direct G=(N, A) un graf conex fără bucle(circuite compuse din mai puțin de 3 muchii), cu două vârfuri speciale s intrarea și t ieșirea (în s nu intră nici un arc și din t nu iese nici un arc) și cu un număr ne-negativ asociat fiecărui arc( sau muchie) care reprezintă capacitatea. N reprezintă o mulțime de elemente x, y,…, și A o submulțime de perechi ordonate (x, y), unde x, y sunt din N. Se presupune că N este o mulțime finită. Elementele lui N se numesc noduri sau vârfuri, iar elementele lui A se numesc arce sau muchii.

O rețea se numește direcționată dacă fiecare arc are o orientare specificată. Uneori vom considera și rețele ne-direcționate, pentru care mulțimea A este o mulțime de perechi ne-ordonate de noduri, adică în care unele arce sunt direcționate altele nu. În cazul nostru vom presupune că fiecare arc al rețelei este direcționat și este de forma perechea (x, y) cu xy. În general se consideră că există un singur arc de la x la y, altfel trebuind să se specifice.

Fie x1, x2,…, xn (n2) o secvență de noduri distincte ale rețelei astfel încât perechea (xi,xi+1) este un arc pentru i=1,..,n-1. Secvența de noduri si arce

x1, (x1,x2), x2,…, (xn-1,xn), xn

se numește lanț de la x1la xn sau uneori lanț direct. Daca xn=x1 atunci secvența (1.1) se numește ciclu direct.

Vom exemplifica noțiunile introduse pentru rețeaua din figura 1.1

În figura 1.1 avem nodurile s, x, y, t și arcele (s, x), (s, y), (x, y), (y, x), (x, t), (y, t);

s,(s, x) ,x, (x, t), t formează un lanț de la s la t , iar x ,(x, y) ,y ,(y ,x) ,x este singurul ciclu direct din rețea.

Fie x1,x2,…,xn o secvență de noduri distincte având proprietatea că fie (xi,xi+1) sau (xi+1,xi) este arc pentru i= 1,…,n-1. O astfel de secvența de noduri și arce se numește drum de la x1 la xn. Astfel drumul diferă de lanț prin posibilitatea de a traversa un arc în direcția opusa orientării lui de la x1 la xn ( pentru rețelele ne-direcționate cele două noțiuni coincid). Arcele (xi,xi+1) care aparțin drumului sunt arce de înaintare iar celelalte (xi+1,xi) sunt arce de întoarcere. De exemplu, secvența s, (s, y),y ,(x, y) ,x ,(x, t) ,t este un drum de la s la t în figura 1.1; conține arcele de înaintare (s, y) , (x, t) și arcul de întoarcere (x,y). Dacă în definiția drumului specificăm că x1=xn secvența rezultată de noduri și arce este un ciclu.

Pentru o rețea (N, A) vom definii matricea de adiacență nod-arc după cum urmează; punem nodurile rețelei pe verticală și arcele pe orizontală și punem în coloana corespunzătoare arcului (x, y), un 1 în rândul corespunzător nodului x, și –1 în rândul corespunzător nodului y și zerouri în rest. De exemplu, rețeaua din figura 1.1 are matricea de incidența:

(s, x) (s, y) (x, y) (y, x) (x, t) (y, t)

s 1 1 0 0 0 0

x -1 0 1 -1 1 0

y 0 -1 -1 1 0 1

t 0 0 0 0 -1 -1

În această matrice sunt trecute toate informațiile în legătură cu structura rețelei.

Dacă xN, notăm A(x) mulțimea tuturor yN astfel încât pentru (x, y)A avem:

A(x)={ yN | (x, y)A }.

Asemănător, notăm B(x) mulțimea tuturor yN astfel încât pentru (y, x)A avem:

B(x)={ yN | (y, x)A }.

A(x) se mai notează cu Г +(x) și B(x) cu Г -(x) .

De exemplu, în rețeaua din figura 1.1, A(s)={x, y}, B(s)=.

2.Fluxuri în rețele

Fiind dată o rețea G=(N,A), presupunem că fiecare arc (x, y)A are asociat un număr real ne-negativ c(x, y) care se numește capacitatea arcului (x, y). Intuitiv acest număr reprezintă capacitatea maximă de mărfuri ce sosesc în y de la x într-o unitate de timp. Funcția c :AR+ se numește funcția capacitate (uneori este mai convenabil ca arcele să aibă capacități infinite).Pentru un arc (xi,xj) capacitatea lui se mai notează cu qij.

În continuare ne vom ocupa de fluxurile statice care sunt definite astfel:

Fie s și t doua noduri distincte aparținând lui N. Un flux static de valoare v de la s la t în (N,A) este o funcție :AR+ care satisface ecuațiile liniare și inegalitățile :

v, x = s,

(2.1) (x, y) – (y ,x) = 0, xs, t,

yA(x) yB(x) -v, x = t

(2.2) (x, y) c(x, y) (x, y)A

Vom numii s intrarea rețelei(în s nu intra nici un arc adică B(s)=) , t ieșirea rețelei (din t nu iese nici un arc adică A(t)= ) și alte noduri intermediare. Dacă fluxul care iese din x este definit astfel:

(x, y) – (y, x),

yA(x) yB(x)

atunci ecuația 2.1 ne arată că fluxul care iese din intrarea s este v, fluxul care iese din t este -v(sau fluxul care intră în t este v) și fluxul care intră într-un nod intermediar este egal cu fluxul care iese din el. O astfel de ecuație care se referă la nodurile intermediare se numește condiție de conservare a fluxului ( =) și ecuația (2.2) se numește condiția de mărginire a fluxului.

Vom mai nota valoarea fluxului si cu v() în loc de v. Se observa ca fluxul de la s la t de valoare v este fluxul de la t la s de valoare -v.

Vom reprezenta un flux de la s la t în figura 2.1, unde se presupune că valorile capacităților sunt suficient de mari astfel ca să nu existe probleme.

Fie un flux, ne referim la (x, y) ca fiind fluxul in arcul (x, y) sau arc-flux. De multe ori vom mai nota, pentru un arc (xi, xj), fluxul pe acest arc cu ij și fluxul cu ξ . Fiecare arc-flux (x, y) apare în exact doua ecuații ale lui (2.1), și are coeficientul 1 în ecuația corespunzătoare nodului x, coeficientul –1 în ecuația corespunzătoare nodului y. Cu alte cuvinte matricea coeficienților ecuațiilor (2.1), fără coloana corespunzătoare lui v, este matricea nod-arc a rețelei.

Problema fluxului maxim static este aceea de a maximiza variabila v în funcție de constrângerile fluxului (2.1) și (2.2). Fie A1,….,Am arce ale rețelei, iar fiecare arc Ai având capacitatea c(Ai); și fie C1,…, Cn lanțuri directe de la s la t. Vom forma matricea de indici (ai,j) pentru arce și lanțuri de dimensiune mn astfel:

1, daca AiCj

(2.3) ai,j= 0, altfel

Fie h o funcție de la mulțimea de lanțuri C1,…, Cn cu valori reale ne-negative care satisface următoarea inegalitate :

(2.4) ai,j h(Cj) c(Ai), i = 1,..,m

Funcția h se numește fluxul de la s la t intr-o forma arc-lanț și h(Cj) fluxul lanț sau fluxul în lanțul Cj . Valoarea lui h este:

v(h)=h(Cj)

3. Notații

Pentru a simplifica notația, facem următoarea convenție. Dacă X și Y sunt submulțimi ale lui N, notăm cu (X, Y) mulțimea tuturor arcelor ce duc de la xX la yY; și, pentru funcție g:A R , fie

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

În mod asemănător, când întâlnim funcția h definită pe noduri din N, facem următoarea notație:

h(x) = h(X).

Dacă X conține doar un singur nod x, vom scrie (x, Y), g(x, Y) ș.a.m.d. Se definește , , . Astfel XY este o mulțime de noduri din X sau Y, XY este o mulțime de noduri și din X și din Y și XY noduri din X care nu aparțin lui Y. De exemplu complementul

lui X în N este =N-X.

Dacă X, Y, Z N atunci:

g(X, YZ)=g(X, Y)+g(X, Z)- g(X, YZ),

g(YZ, X)=g(Y, X)+ g(Z, X)-g(YZ, X).

Pentru că Y și Z sunt disjuncte avem:

g(X, YZ)=g(X, Y)+g(X, Z),

g(YZ, X)=g(Y, X)+ g(Z, X).

Se observă că:

(B(x), x)=(N, x),

(x, A(x))=(x, N),

și

g(N, X)= g(N, x)= g(B(x), x)

g(X, N)= g(x, N)= g(x, A(x)).

4.Tăieturi

Se numește tăietură C în (N, A) care separă s și t o mulțime (X,), unde sX și t. Capacitatea tăieturii (X,) este c(X,).

De exemplu, mulțimea de arce C={(s, y), (x, y), (x, t)} cu X={s, x}, este o tăietura în rețeaua din figura 1.1 care separa s de t.

Se observă că orice lanț de la s la t trebuie să conțină câteva arce din fiecare tăietură (X,X). Fie x1,x2,…,xn un lanț cu x1=s și xn =t .

Deoarece x1X , xnX, există un xi (1 i< n) cu xiX, xi+1X. Deoarece arcul (xi, xi+1) tăieturii (X, X) .Rezultă c(X).

Dacă X conține doar un singur nod x, vom scrie (x, Y), g(x, Y) ș.a.m.d. Se definește , , . Astfel XY este o mulțime de noduri din X sau Y, XY este o mulțime de noduri și din X și din Y și XY noduri din X care nu aparțin lui Y. De exemplu complementul

lui X în N este =N-X.

Dacă X, Y, Z N atunci:

g(X, YZ)=g(X, Y)+g(X, Z)- g(X, YZ),

g(YZ, X)=g(Y, X)+ g(Z, X)-g(YZ, X).

Pentru că Y și Z sunt disjuncte avem:

g(X, YZ)=g(X, Y)+g(X, Z),

g(YZ, X)=g(Y, X)+ g(Z, X).

Se observă că:

(B(x), x)=(N, x),

(x, A(x))=(x, N),

și

g(N, X)= g(N, x)= g(B(x), x)

g(X, N)= g(x, N)= g(x, A(x)).

4.Tăieturi

Se numește tăietură C în (N, A) care separă s și t o mulțime (X,), unde sX și t. Capacitatea tăieturii (X,) este c(X,).

De exemplu, mulțimea de arce C={(s, y), (x, y), (x, t)} cu X={s, x}, este o tăietura în rețeaua din figura 1.1 care separa s de t.

Se observă că orice lanț de la s la t trebuie să conțină câteva arce din fiecare tăietură (X,X). Fie x1,x2,…,xn un lanț cu x1=s și xn =t .

Deoarece x1X , xnX, există un xi (1 i< n) cu xiX, xi+1X. Deoarece arcul (xi, xi+1) tăieturii (X, X) .Rezultă că dacă toate arcele unei tăieturi ar fi șterse din rețea , atunci nu mai există nici un lanț de la s la t și valoarea fluxului maxim pentru noua rețea ar fi 0.

Din moment ce o tăietura blochează toate lanțurile de la s la t este clar că valoarea v a fluxului nu poate depăși capacitatea nici unei tăieturi , fapt ce va fi demonstrat din (2.1) și (2.2).

LEMA 4.1 Fie un flux de la s la t într-o rețea (N, A), și având valoarea v. Dacă

(X, X) este o tăietură ce separa s de t, atunci:

v =(X, X) -(X, X) c(X, X).

Demonstrație: Deoarece este un flux, satisface ecuațiile :

(s, N)-(N, s) =v,

(x, N) -(N, x) =0, xs, t,

(t, N) -(N, t) = -v,

Acum vom însuma aceste ecuații în funcție de xX .Deoarece sX și t, rezultatul va fi:

v =((x, N) -(N, x))= (X, N) -(N, X)

Înlocuind N cu XX în aceste egalități va rezulta:

v=(X, X X) – ( X X, X) =(X, X) +(X, X)-(X, X)-(X, X),

aceasta verificând egalitatea din (4.1) .Deoarece (X, X) 0 și (X, X) c(X,) din (2.2) rezulta imediat inegalitatea din (4.1).

q.e.d.

Cu alte cuvinte, egalitatea din (4.1) ne spune că valoarea unui flux de la s la t este egală cu fluxul ce trece prin rețea de-a lungul oricărei tăieturi ce separa s și t.

5 .Flux maxim

Din condiția de conservare a fluxului rezultă fluxul care iese din s, notat 1, este egal cu fluxul care intră în t, notat cu n. Problema fluxului maxim este problema determinării unui flux definit pe mulțimea arcelor rețelei de transport A, astfel încât fluxul n care intră în ieșirea rețelei, t, să aibă valoarea cea mai mare posibilă.

TEOREMA 5.1( Teorema Ford-Fulkerson) Pentru orice rețea valoarea fluxului maxim de la s la t este egală cu capacitatea minimă a tăieturilor ce separă s de t.

Înainte de a demonstra această teorema vom da un exemplu. Considerăm rețeaua din figura 1.1 cu capacitățile c si funcția cele indicate în figura 5.1, c(x, y) fiind primul număr din perechea scrisă pe arcul (x, y), si (x, y) al doilea .În acest exemplu fluxul este 3. Deoarece tăietura formată din arcele (s, x), (y, x) și (y, t) are de asemenea capacitatea 3, rezultă din lema 4.1. că fluxul este maxim si tăietura minimă.

Demonstrație 5.1 Din lema 4.1., este suficient să stabilim existența unui flux și o tăietură (X,) pentru care are loc egalitatea dintre valoarea fluxului și capacitatea tăieturii. Stabilim acestea prin luarea fluxului (care sigur există) și definim, în funcție de , o tăietură (X,) astfel încât :

(X,)=c(X,), (,X)=0, și se verifică egalitatea din (4.1).

Astfel, fie un flux maxim. Folosind , definim recursiv mulțimea X după cum urmează:

sX;

dacă xX si (x, y)<c(x, y), atunci y X;

dacă xX si (y, x) > 0, atunci yX.

Să presupunem că t.Rezultă din definiția lui X că există un drum de la s la t,

s=x1, x2,…, xn=t,

având proprietatea că toate arcele de înaintare(xi,xi+1) ale drumului,

(xi,xi+1)<c(xi,xi+1),

și pentru cele de întoarcere (xi+1,xi) ale drumului ,

(xi+1,xi)> 0.

Fie ε1minimul lui c- pentru arcele de înaintare ale drumului, și ε2 minimul lui pentru arcele de întoarcere, și fie =min(1,2)>0. Să modificăm fluxul după cum urmează: îl mărim pe cu pentru toate arcele de înaintare. Se verifică ușor că noua funcție astfel definită este un flux de la s la t având valoarea v+. Dar nu este maximal, contrar a ce am presupus mai sus, și astfel t.

În consecință (X, ) este o tăietură ce separă s de t. Mai mult, din definiția lui X rezultă că:

(x,)=c(x,) pentru. (x,) (X, ),

( , x)=0 pentru (, x) ( , X),

din moment ce X. Astfel

(X, )=c(X, ), (, X)=0,

obținându-se egalitatea din (4.1).

q.e.d.

Din lema 4.1., teorema 5.1. și demonstrațiile acestora pot fi obținute o serie de corolare.

Vom numi un drum de la s la t flow augmentig path cu privire la un flux ,un drum pe care putem modifica fluxul de la s la t; în acest drum pe arcele de înaintare(arcele în direcția de la s la t) avem <c, și pe arcele de întoarcere(în direcția de la t la s) avem >0.

COROLAR 5.2. Un flux este maxim dacă și numai dacă nu există un flow augmentig path cu privire la .

Demonstrație. Dacă este maxim, atunci sigur nu există un flow augmentig path. Presupunem contrariul, că nu există un flow augmentig path. Atunci mulțimea X definită recursiv folosind ca în demonstrația teoremei 5.1. nu poate conține nodul de ieșire t. Deci, ca în demonstrația teoremei 5.1., (X, ) este o tăietură care separă s de t având capacitatea egală cu valoarea lui . În consecință este maxim.

q.e.d.

Corolarul 5.2. are importanță fundamentală în studiul fluxurilor în rețea. Se spune că pentru a mării valoarea unui flux, este suficient să căutăm să îmbunătățim “ceva mai restrictiv”.

Spunem că un arc(x, y) este saturat cu privire la un flux dacă (x, y)=c(x, y) și se numește fără flux cu privire la fluxul dacă (x, y)=0. Astfel dacă un arc este și saturat și fără flux are capacitatea 0. Corolarul 5.3. caracterizează o tăietură în termenii dați mai sus.

COROLAR 5.3. O tăietură (X, ) este minimă dacă și numai dacă fiecare flux maximal saturează toate arcele lui (X, ) pe când toate arcele lui (,X) sunt fără flux cu privire la fluxul .

COROLAR 5.4. Fie (X, ) și (Y, ) tăieturi minime. Atunci (XY, ) și (XY, ) sunt și ele tăieturi minime.

Următoarea teoremă ne arată că tăietura minimă (X, ) utilizată în demonstrația teoremei 5.1. nu depinde de fapt de fluxul maxim .

TEOREMA 5.5. Fie (Y, ) o tăietură minimă, un flux maxim, și (X, ) fiind tăietura minimă relativă la din demonstrația teoremei 5.1. Atunci XY.

Demonstrație. Presupunem că X nu e inclus în Y. Atunci (X Y)X, și (XY, ) este o tăietură minimă din corolarul 5.4. . Fie x un vârf din X care nu este în XY. Deoarece x X și xs, există un drum de la s la x, s=x1, x2,…,xk=x, astfel încât fiecare arc de înaintare al drumului este nesaturat cu privire la , în timp ce fiecare arc de întoarcere are un flux pozitiv. Dar deoarece s XY și x , există o pereche xi, xi+1 (1i<k) unde xi XY, xi+1 . Dacă (xi, xi+1) este un arc de înaintare al drumului, atunci (xi, xi+1)<c(xi, xi+1), contrazicând corolarul 5.3. În mod similar dacă (xi, xi+1 ) este un arc de întoarcere al drumului, corolarul 5.3. este contrazis. Deci XY.

q.e.d.

Astfel dacă (Xi, i+1), i=1,…,m, sunt toate tăieturile minimale ce separă intrarea de ieșire, mulțimea X definită relativ la un flux în demonstrația teoremei 5.1 este intersecția tuturor Xi și deci nu depinde de selecția fluxului.

Cu toate că tăietura minimă care a fost utilizată în demonstrația teoremei 5.1 printr-o definiție recursivă a mulțimii de intrări X, în mod asemănător putem genera o tăietură minimă (Y, ) prin definirea mulțimii de ieșiri în termenii unui flux maximal astfel:

(a’) t ;

(b’) Dacă y și (x, y)<c(x, y), atunci x ;

Dacă y și (y, x)>0, atunci x .

În mod echivalent, putem inversa orientările tuturor arcelor și fluxurile arcelor, prin schimbarea intrării cu ieșirea astfel încât t devine intrare și s devine ieșire, și apoi folosim definiția dată în teorema 5.1 ca să construim . Cu toate că definiția e relativă la un flux maxim particular, mulțimea nu depinde de fapt de alegere, din moment ce este intersecția mulțimilor ale tăieturilor minime (Xi, ) .

Utilizând ambele definiții, putem stabilii un criteriu de unicitate a tăieturii minime.

TEOREMA 5.6 Fie X mulțimea tuturor vârfurilor definită în demonstrația teoremei 5.1, si fie mulțimea definită mai sus, și presupunem că c este strict pozitiv. Tăietura minimă (X,) este unică dacă și numai dacă (X,)= (Y, ).

Demonstrație Trebuie să arătăm că dacă (X,)= (Y, ), și dacă (Z,) este o tăietură minimă, atunci (X,)= (Z,).

Inițial se observă că dacă (X,)= (Y, ), atunci amândouă sunt egale cu (X,). Dacă XY din teorema 5.5, atunci (X,) (Y, ). Pe de altă parte, dacă (u, v) (X,)= (Y, ), unde u X și v , deci (u, v) (X,).

Pentru o tăietură minimă arbitrară (Z,), obținem tot din teorema 5.5 și analoaga ei pentru (Y, ), că XZ, . Astfel (X,)(Z,) (Z,). Deci c(X,)c(Z,). Dacă (X, )( Z,), atunci ori unele arce din (Z,) au capacitatea 0, contrazicând presupunerea noastră că c>0, ori c(X,) c(Z,), contrazicând minimalitatea lui (Z,).Astfel (X,)= (X,)= (Z,).

q.e.d.

De observat că teorema 5.6. nu este valabilă dacă presupunerea c>0 se schimbă cu c0. De exemplu, în rețeaua din figura 5.2., X={s}, ={t},

și (X, )=(Y, )=(s, t). Cu toate acestea, (Z, ) cu Z={s, x}este o altă tăietură minimă

care conține ambele arce.

6.Mulțimi deconectoare și tăieturi

Am caracterizat tăieturile ca mulțimi de arce de forma (X, ) cu s X, t , și am observat că o tăietură blochează toate lanțuri de la s la t. Astfel, numim o mulțime de arce o mulțime deconectoare dacă are proprietatea de a bloca lanțuri, deci fiecare tăietură este o mulțime de deconectare. Reciproca, însă, nu este în mod necesar adevărată. De exemplu, mulțimea tuturor arcelor dintr-o rețea este o mulțime deconectoare, dar nu este o tăietură.

Că orice mulțime deconectoare conține o tăietură poate fi ușor de observat și din cele ce urmează. Fie D mulțimea deconectoare, și definim o submulțime X de noduri după următoarele reguli:

s X;

dacă x X și (x, y) A-D, atunci y X.

Este evident că t și (X, )D. De observat că D este o mulțime propriu-zis deconectoare, ce înseamnă că este o mulțime care nu are submulțimile propriu-zis deconectoare, atunci (X, ) =D. Astfel orice mulțime deconectoare este o tăietură, reciproca nu este întotdeauna adevărată. De exemplu, în fig 5.2., tăietura (X, ) cu X={s, x} nu este o mulțime propriu-zis deconectoare.

Putem sintetiza tot ce am scris mai sus astfel:

clasa mulțimilor propriu-zis deconectoare este inclusă în clasa tăieturilor, care, în schimb, este inclusă în clasa mulțimilor deconectoare, și fiecare din aceste incluziuni sunt stricte;

fiecare mulțime deconectoare conține o tăietură.

Rezultă că noțiunea de tăietură poate fi înlocuită fie cu o mulțime deconectoare sau fie cu o mulțime propriu-zis deconectoare în termenii teoremei Ford-Fulkerson.

Tăieturile pot fi folosite mai ușor când avem de-a face cu fluxuri în formă nod-arc, iar mulțimile deconectoare pot fi folosite convenabil în cazul problemei fluxului maxim în forma arc-lanț.

7. Metoda de etichetare a nodurilor pentru rezolvarea problemei de flux maxim

Demonstrația teoremei Ford-Fulkerson din § 5 ne oferă un algoritm simplu și eficient de construire a fluxului maxim și a tăieturilor minime în rețea [5].

Algoritmul poate fi inițializat cu flux zero, continuând cu o secvență de “etichetare” ( Pas A de mai jos), în care caz, fie rezultă un flux de o valoare mai mare (Pas B de mai jos), fie se termină datorită faptului că prezentul flux este maxim.

Pentru a asigura terminarea algoritmului, vom presupune că funcția capacitatea c ia valori întregi ne-negative. Problema determinării fluxului maxim cu componente numere raționale într-o rețea cu numere raționale, se reduce la cazul când componentele fluxului, cât și capacitățile arcelor sunt numere întregi ne-negative, deoarece putem amplifica atât capacitățile arcelor cât și componentele fluxului cu aceeași cantitate pozitivă.

O etichetă are una din formele (x+, ) sau (x¯, ), unde x N și este un număr întreg pozitiv sau , potrivit regulilor definite în Pas A.

În Pasul A, un nod este considerat a fi în una din cele trei stări, ne-etichetat, etichetat și scanat (are o etichetă și toate arcele adiacente lui au fost vizitate), sau etichetat și ne-scanat (are o etichetă dar nu toate arcele adiacente lui au fost vizitate). Inițial toate nodurile sunt ne-etichetate.

Pasul A începe prin etichetarea intrării s cu eticheta (-, (s)=) (sursa este acum etichetată și ne-scanată; toate celelalte noduri fiind ne-etichetate). Să selectăm un nod oarecare x, etichetat și ne-scanat, și să presupunem că este etichetat (z, (x)). Nodurilor y ce sunt ne-etichetate, și (x, y)<c(x, y), li se atribuie eticheta (x+, (y)), unde:

(y)=min[(x),c(x, y)- (x, y)].

(Astfel y este etichetat și ne-scanat). Pentru toate nodurile y, ce sunt ne-etichetate, și (y,x)>0 , li se atribuie eticheta (x, (y)), unde:

(7.2) (y)=min[(x), (y, x)].

(Astfel y este etichetat și ne-scanat și x este acum etichetat și scanat.)

Procedeul se repetă până când ieșirea t este etichetată și ne-scanată, sau până când nu mai poate fi etichetat nici un nod, iar ieșirea este ne-etichetată. În primul caz se trece la Pas B, în celălalt caz algoritmul se termină.

Pas B(modificarea fluxului). Ieșirea t a fost etichetată (y, (t)). Dacă t este etichetat (y+, (t)), se înlocuiește (y, t) cu (y, t)+(t); dacă t este etichetat (y, (t)), se înlocuiește (t, y) cu (t, y)-(t). Apoi, ne îndreptăm atenția asupra nodului y. Dacă y este etichetat (x+, (y)), se înlocuiește (x, y) cu (x, y)+(t), iar dacă este etichetat cu (x, (y)) se înlocuiește (y, x) cu (y ,x)-(t), și se continuă cu nodul x. Se modifică fluxul până când se ajunge la intrarea s, se ignoră vechile etichete și se reia Pasul A.

Procesul de etichetare este o căutare sistematică a unui flow augmenting chain de la s la t (Corolarul 5.2). În etichete se află destulă informație, astfel dacă ieșirea este etichetată modificarea fluxului de-a lungul drumului se poate face rapid. Dacă, pe de altă parte Pasul A se termină și ieșirea nu este etichetată, fluxul maxim și mulțimea arcelor dintre nodurile etichetate și cele ne-etichetate formează o tăietură minimă, nodurile etichetate corespunzând mulțimii X definită în demonstrația teoremei 5.1.

Un motiv principal al eficienței procesului de etichetare este acela că odată un nod etichetat și scanat acesta poate fi ignorat pentru restul procesului. Etichetarea unui nod x corespunde cu localizare unui drum de la s la x care poate fi segmentul inițial dintr-un flow augmentig path. Putând fi mai multe astfel de drumuri de la s la x, găsirea unuia este suficientă.

Dacă fluxul este întreg și Pasul A se termină cu etichetarea ieșirii t, atunci modificare fluxului cu (t) din Pasul B, fiind minimul dintre întregii pozitivi, este un întreg pozitiv. Deci, dacă calculul este inițiat cu un flux întreg, fiecare flux ce urmează este întreg. În consecință algoritmul este finit, din moment ce valoarea fluxului crește cu cel puțin o unitate cu fiecare etichetare a ieșirii t; la terminarea algoritmului vom avea un flux maxim care este întreg.

TEOREMA 7.1 (Teorema de integritate). Dacă funcția capacității c este o valoare întreagă, atunci există un flux maxim care este tot întreg.

Următorul exemplu ilustrează utilizarea metodei de etichetare pentru determinarea fluxului maxim.

Exemplu.

Fie rețeaua din figura 1.1 cu capacitățile arcelor și fuxul inițial indicate în figura 7.1, perechea c(x, y), (x, y) fiind scrisă în vecinătatea arcului (x, y).

Începem Pasul A prin atribuirea nodului s a etichetei (_,) vezi figura 7.2. De la s,

se etichetează y cu (s+,3), astfel completând etichetarea de la s. De la y, x poate fi etichetat (y+, 1) (sau (y-, 1)), și este singurul nod ne-etichetat care poate fi etichetat din y. Din nou se selectează un nod etichetat și ne-scanat (x este singurul de acest fel) și continuăm să atribuim etichete. Se observă că ieșirea t poate fi etichetată (x+, 1). Aceasta localizează un flow augumenting path, găsit prin refacerea drumului invers de la ieșire conform direcțiilor date în etichete, de-a lungul căruia se poate modifica fluxul cu (t)=1. Aici drumul este lanțul s, y, x, t. Noul flux de valoare 2 este ilustrat în figura 7.3.

Acum se șterg vechile etichete și se repetă algoritmul de etichetare. De data aceasta se obțin etichetele ilustrate în figura 7.3. Din nou este etichetată ieșirea t și fluxul, poate fi îmbunătățit cu (t)=1 de-a lungul drumului s, (s, y), y, (x, y), x, (x, t), t, obținându-se fluxul din figura 7.4.

Repetarea Pasului A are ca rezultat ne-etichetarea ieșirii t, mulțimea de noduri etichetate fiind ilustrată în figura 7.4. Astfel fluxul din figura 7.4 este maxim și tăietura minimă este formată din arcele (s, x), (y, x), (y, t).

Etichetarea în sens invers de la ieșire conform regulilor (a’), (b’) din §5 identifică aceiași tăietură, și deci conform teoremei 5.6 aceasta este singura tăietură ce separă s de t.

Încheiem aceasta parte cu un exemplu ce ilustrează că algoritmul de etichetare poate să nu se termine dacă capacitățile arcelor sunt iraționale. În special exemplul ilustrează faptul că dacă algoritmul nu este interpretat cu destulă strictețe pentru a permite selectarea oricărui flow augumenting path la fiecare etapă, atunci terminarea într-un timp finit se poate să nu aibă loc pentru capacități iraționale.

Înainte de a prezenta acest exemplu vom da o definiție ce ne va ajuta în prezentare. Dacă (N, A) este o rețea cu funcția capacității c, și dacă este un flux de la s la t în (N, A) , atunci c(x, y)- (x, y) este capacitatea reziduală a arcului (x, y) cu privire la .

Să considerăm recurența

an+2=an-an+1.

Această recurență are o soluție an= rn, unde r=(-1+ )/2<1. Astfel seria converge la suma S. Construim o rețea directă cu patru “arce speciale”:

A1=(x1, y1),

A2=(x2, y2),

A3=(x3, y3),

A4=(x4, y4),

și arcele adiționale (yi, yj), (xi, yj), (yi, xj), pentru i j , împreună cu arcele intrare (s, xi) și arcele ieșire (yj, t). Aceste patru arce speciale au capacitățile a0, a1, a2, a3; toate celelalte arce având capacitatea S.

Pas 1. Se caută un lanț de la s la t care include, dintre arcele speciale, doar A1, și impunem un flux a0 în acest lanț. De exemplu, lanțul s, x1, y1,t. (Aceste arce speciale au capacitatea reziduală 0, a1, a2, a3, respectiv).

Pasul inductiv. Să presupunem că arcele A’1, A’2, A’3, A’4 (câteva din combinațiile arcurilor A1, A2, A3, A4) au capacitățile reziduale 0, an+2, an+1, an+1. Căutăm un lanț de la s la t arc ce conține printre arcele speciale, doar A’2 și A’3 și impunem an+1 unități adiționale de flux de-a lungul acestui lanț. De exemplu, lanțul s, x’2, y’2, x’3, y’3, t. (Arcele speciale au acum capacitățile 0, an-an+1=an+2, 0, an+1.)

Apoi căutăm un drum de la s la t ce conține A’2 ca arc de înaintare, A’1 și A’3 ca arce de întoarcere, ultimele fiind ultimele arce de întoarcere din drum, și impunem un flux adițional de an+2 unități de-a lungul drumului. De exemplu, drumul s, x’2, y’2, y’1, x’1, y’3, x’3, y’4, t conținând arcele de întoarcere (y’1, x’1), (y’3, x’3). (Arcele speciale acum au capacități reziduale an+2, 0, an+2, an+1.).

Pasul inductiv mărește valoarea fluxului cu an+1+an+2=an. Deci pe orice arc ne-special nu este necesar să se transporte mai mult decât=S unități de flux în pasul inductiv . Procesul converge către un flux având valoarea S, unde valoarea fluxului maxim pentru această rețea este 4S.

8.Graf incrementat

Procesul de găsire a unui flow augmenting chain ( lanț de mărire a fluxului )într-un graf când fluxurile arcelor sunt date de un vector, reprezintă procesul de găsire a unui drum de la la într-un graf incrementat definit astfel:

și

unde:

iar capacitatea arcului este

și

iar capacitatea arcului este .

Procedura de etichetare a algoritmului de etichetare descris mai sus nu reprezintă altceva decât o metodă de calcul a mulțimii R(s) (care este mulțimea vârfurilor în care pot ajunge din s) în graful incrementat . Dacă , adică dacă nodul t este etichetat, atunci un drum P de la s la t în graful a fost găsit. Lanțul de mărire a fluxului din G este atunci drumul P unde arcele lui sunt arcele de înaintare iar arcele lui sunt arcele de întoarcere.

Figura 8.1(a) ilustrează fluxul din graful G, unde numerele subliniate sunt fluxurile, și numerele alăturate arcelor sunt capacitățile lor. Figura 8.1(b) ilustrează graful incrementat corespunzător.

9.Descompunerea fluxului

Este uneori de dorit să reprezentăm un flux complex ca sumă de fluxuri mai simple. Această descompunere este utilă nu atât faptului că este necesară în practică, ci mai ales faptului că ajută la o mai bună înțelegere a fluxurilor în rețele și servește la justificarea algoritmilor de fluxuri în rețele.

Să notăm cu fluxul în graful G în care arcele au și arcele au . Evident, nu este un flux pentru orice mulțime arbitrară de arce S din moment ce un flux trebuie să satisfacă ecuațiile

dacă xi= s

(9.1.) – = – dacă xi= t 0 dacă xis sau t

pentru o valoare a lui v. Dacă reprezintă un flux, mulțimea S a arcelor trebuie să formeze ori un drum în G de la s la t, ori un circuit în G.

Fiind date două fluxuri și , să notăm cu fluxul pentru care fluxul pe arcul este .

TEOREMA 9.1. Dacă este un flux de la s la t de valoare (întreagă) v în graful G, atunci poate fi descompus astfel:

, unde sunt drumuri elementare de la s la t în graful G și sunt circuite elementare ale lui G.

( și nu sunt neapărat distincte).

Demonstrație. Pornind de la graful cu fluxul construim graful unitar astfel: mulțimea de vârfuri ale lui este aceeași cu mulțimea N de vârfuri ale lui G. Dacă este fluxul în arcul din G, atunci construim arce între vârfurile și din care vor avea fluxurile unitare. Dacă , atunci nu vom pune nici un arc între și . Graful este atunci un s – graf și din moment ce fiecare arc din corespunde unei unități de flux pe arc din graful G, reprezintă fluxul în G.

În graful gradele vârfurilor trebuie (datorită condițiilor de continuitate 9.1) să satisfacă:

sau

Acum dacă v arce de întoarcere sunt adăugate lui de la vârful la , graful va avea un circuit Euler-ian (folosește toate muchiile). Scoaterea acestor v arce din circuitul Euler-ian lasă v drumuri de la la care în totalitate traversează fiecare arc din o singură dată. Fie aceste drumuri . Drumurile ’ nu sunt neapărat elementare cu toate că (prin definiția circuitului Euler-ian), trebuie să fie simple. Cu toate acestea, din moment ce orice drum ne-elementar poate fi considerat ca sumă de drumuri elementare de la la și un număr de circuite elementare care nu au arce comune obținem:

,

unde sunt drumuri elementare de la la și sunt circuite elementare. Astfel s-a demonstrat teorema.

În general nu toate drumurile și circuitele sunt distincte. Dacă doar primele drumuri și circuite sunt distincte, unde drumul apare de ori în lista și circuitul apare de ori în lista , atunci poate fi scris astfel:

unde suma sugerează fluxul adițional după cum am explicat mai sus.

În cadrul demonstrației teoremei 9.1, un alt rezultat important este obținut și anume acela că fluxurile unitare în care a fost descompus sunt „conformal”, adică dacă este fluxul pe arcul al lui G, atunci există un număr de fluxuri unitare , toate utilizând acest arc în direcția de la la.

Figura 9.1 ilustrează un exemplu de flux ξ și descompunerea lui în drumuri și circuite elementare de la s la t

CAPITOLUL II

VARIAȚII ALE PROBLEMEI FLUXULUI MAXIM.

1. Intrări și ieșiri multiple

Cu toate că presupunerea a fost că rețeaua are o singură intrare și o singură ieșire, este ușor de observat că situația în care avem mai multe intrări și ieșiri într-o rețea, putând avea fluxuri de la orice intrare la orice ieșire, nu prezintă o noutate, din moment ce legarea de două noi noduri prin câteva arce de intrările și ieșirile multiple reduc problema la cazul unei rețele cu o singura intrare și o singură ieșire.

Mai detaliat, să presupunem că nodurile N ale rețelei (N,A) sunt partiționate în trei mulțimi:

S (mulțimea intrărilor),

T (mulțimea ieșirilor),

R (mulțimea nodurilor intermediare),

și considerăm problema găsirii fluxului maxim de la S la T.

Un flux de la S la T poate fi considerat ca fiind o funcție reală definită pe A ce satisface:

(1.1) (x, N) – (N, x)=0 pentru x R,

(1.2) 0 (x, y) c(x, y) pentru (x, y) A,

valoarea fluxului fiind:

(1.3) v= (S, N)- (N, S).

Vom extinde (N,A) la o rețea (N*,A*) prin adăugarea a două noduri u, v și a tuturor arcelor (u, S), (T, v), și funcția de capacitate c definită pe A va fi c* definită pe A* astfel:

c*(u, x)=, x S,

c*(x, v)= , x T,

c*(x, y)=c(x, y), (x, y) A.

Astfel restricția a fluxului * de la u la v în (N*,A*) este un flux de la S la T în

(N,A). Invers un flux de la S la T în (N,A) poate fi extins la un flux * de la u la v în (N*,A*) dacă definim :

*(u, x)= (x, N)- (N, x), x S,

*(x, v)= (N, x)- (x, N), x T,

*(x, y)= (x, y), altfel.

În consecință problema fluxului maxim de la S la T în (N,A) este echivalentă cu problema intrării și ieșirii unice pentru rețeaua extinsă.

Tăieturile importante pentru cazul cu multe intrări S și ieșiri T sunt acelea care separă S și T: o mulțime de arce (X, ) cu S X, T. Termenul de mulțime deconectoare, va fi o mulțime de arce care blochează toate lanțurile de la S la T. Teorema lui Ford-Fulkerson și corolarele ei, ca și celelalte teoreme din §5, rămân valabile făcând modificările de rigoare.

În situația în care există mai multe intrări și ieșiri, dar în care anumite intrări se pot “duce” la anumite ieșiri, problema este complet diferită. Pentru o astfel de problemă, ce poate fi gândită în termenii fluxului simultan a unor bunuri, valoarea fluxului maxim poate fi mai mică decât capacitatea minimă a mulțimii deconectoare. Aici o mulțime deconectoare înseamnă o mulțime de arce care blochează toate lanțurile de la intrări la ieșirile corespunzătoare. De exemplu, considerăm rețeaua din figura 1.1:

cu intrările s1,s2,s3, și ieșirile t1,t2,t3. Fiecare arc are capacitate unitară. Să presupunem că si, ti (i=1,2,3) este intrarea și respectiv ieșirea pentru bunul i . Atunci valoarea fluxului maximal este 3/2, obținut prin transmiterea unui flux de jumătate de unitate, din bunul i, pe unicul lanț de la si la ti . În orice caz, arcele (x, y) și (y, z) formează o mulțime deconectoare minimă având capacitatea 2. Deci fluxul maxim este mai mic decât capacitatea mulțimii deconectoare minime(3/2 <2).

2. Limitele inferiore ale fluxului pe arce

Cu toate că limita inferioară zero a fost presupusă pentru toate fluxurile de pe arce, nu este o condiție cu adevărat necesară pentru determinarea fluxului maxim. Dacă condițiile :

(2.1) 0 (x, y)c(x, y)

sunt înlocuite cu :

l(x, y) (x, y)c(x, y),

unde l este o funcție reală dată, definită pe arcele din A care satisfac:

0l (x, y)c(x, y),

algoritmul de etichetare poate fi schimbat pentru a întâmpina această situație asigurând un flux inițial pentru a începe algoritmul de determinare a fluxului maxim. Poate fi o funcție ce nu satisface ecuațiile (2.1) din capitolul I și inegalitățile (2.2) (ex. Fie l=c în exemplul din paragraful precedent), dar presupunând că aceste constrângeri sunt valabile și pentru valorile întregi l și c, și a fost găsit și un flux inițial ce le satisface, singura schimbare în algoritmul de etichetare fiind următoarea. Dacă x a fost etichetat (z , ), atunci y poate fi etichetat [x, min( , (y, x)-l(y, x))] asigurând (y, x)>l(y, x).

De asemenea se observă ușor că analogul Teorema 5.1 devine:

TEOREMA 2.1 Dacă există o funcție ce satisface atât (2.1) din capitolul I cât și (2.2) pentru niște valori v, atunci valoarea maximă a acestor valori v cu constrângerile date este egală cu minimul diferenței c(X, )- l(X, ) pentru toți XN cu s X, t .

Pe de altă parte, presupunând încă o dată existența unei funcții care satisface (2.1) din capitolul I și (2.2) pentru niște valori v, valoarea minimă a lui v poate fi găsită într-un mod asemănător: dacă x este etichetat cu (z , ) și dacă (x, y)>l(x, y), îl etichetăm pe y cu [x, min( , (x, y)-l(x, y))]; sau dacă (y, x)<c(y, x), y este etichetat cu [x, min( , c(y, x)- (y, x))].

În acest caz analogul teoremei 5.1 este:

TEOREMA 2.2 Dacă există o funcție care satisface (2.1) din capitolul I și (2.2) pentru câteva valori v, valoarea minimă a acestor valori v cu constrângerile date este egală cu maximul diferenței l(X, )- c( , X) pentru toți XN cu s X, t .

O altă abordare a acestei probleme este:

Se consideră un graf G=(N,A) ale cărui arce (xi,xj) au capacitățile (limită superioară a fluxului) qij, și limitele inferioare ale fluxului rij. Să presupunem că dorim să știm dacă există un flux posibil între s și t, adică un flux ξij ce satisface condiția (9.1) din capitolul I

dacă xi= s

(9.1) – = – dacă xi= t 0 dacă xis sau t

și rijξij qij pentru toate arcele (xi,xj) G.

Începem prin introducerea unei intrări artificiale sa și a unei ieșiri artificiale ta în graful G pentru a produce un nou graf Ga. Pentru fiecare arc (xi,xj) cu rij0, introducem un arc (sa,xj) de capacitate rij cu limita inferioară 0, și de asemenea un al doilea arc (xi,ta) de capacitate rijși limită inferioară 0. Micșorăm qij cu rij și pe rij îl facem 0. În plus introducem un arc (t,s) cu qts=și rts=0.

Pentru exemplul din figura 2.1(a) unde doar două arce au limita inferioară diferită de 0, aceste transformări produc graful din figura 2.1(b). Să găsim acum fluxul maxim între sa și ta ale grafului transformat Ga. Dacă valoarea fluxului maxim de la sa la ta este (adică dacă toate arcele care plecă de la sa, și toate arcele care ajung în ta sunt saturate) și, să spunem că fluxul pe arcul (t,s) este ξts; atunci un flux posibil de valoare ξts există în graful inițial. Cu alte cuvinte dacă scoatem rij din fluxul arcelor (xi,ta) și (sa,xj), și dacă adăugăm rij la fluxul arcului (xi,xj) atunci valoarea fluxului total de la sa la ta se reduce cu rij, fluxul în (xi,ta) și (sa,xj) este redus la 0 și fluxul arcului (xi,xj) va lua o valoare rijξijqij. (Valoarea finală a lui ξij =rij dacă valoarea inițială a lui ξij ce corespunde fluxului maxim este 0, și valoarea finală ξij= qij dacă valoarea inițială a lui ξij este maxim posibil, adică qij-rij). Pasul micșorării fluxului maxim este opusul măririi fluxului în algoritmul maximizării fluxului din moment ce am presupus că fluxul maxim de la sa la ta este egal procesul de micșorare a fluxului va reduce fluxul de la sa la ta la 0 (altfel făcând cele două vârfuri și arcele lor incidente inutile), și fluxul din arcele cu rij0 vor verifica rijξijqij. Rezultatul final este deci o “circulație“ a fluxului în graf, valoarea acestui flux fiind ξts.

Pe de altă parte:

TEOREMĂ 2.3. Dacă valoarea fluxului maxim de la sa la ta în graful Ga nu este , atunci nu există un flux posibil în G.

3. Fluxuri în rețele ne-direcționate și mixte

Să presupunem că rețeaua este ne-direcționată sau mixtă, și că fiecare arc are o capacitate ne-negativă. Dacă arcul (x, y) este ne-direcționat cu capacitatea c(x, y), asta înseamnă că :

(x ,y)c(x, y),

(3.1) (y, x)c(x, y),

(x ,y) (y, x)=0.

Asta înseamnă că, (x, y) este fluxul de la x la y în (x, y), și arcul (x, y) are o capacitate c(x, y) în ambele direcții, dar fluxul este permis într-o singură direcție.

De exemplu, ne putem gândi la o rețea de străzi dintr-un oraș, fiecare stradă având o anumită capacitate a traficului, și ne vom întreba; cum pot fi puse semnele de circulație cu sens unic care nu sunt deja orientate, pentru a permite cel mai mare flux de trafic de la o mulțime de puncte la alta?

La o primă privire, poate părea că această problemă va implica studierea unui număr mare de probleme de flux maximal obținute prin orientarea rețelei în diferite moduri. Dar de fapt problema poate fi rezolvată considerând o singură rețea direcționată: și anume aceea obținută prin înlocuirea fiecărui arc ne-direcționat cu o pereche de arce opus direcționate, fiecare având capacitatea egală cu a arcului vechi. Motivul pentru aceasta este acela că, dându-se orice soluție ,v a constrângerilor fluxului (2.1) și (2.2) din capitolul I, poate rezultă o soluție ’, v pentru care:

’(x, y) ’(y, x)=0

luând

‘(x, y)=max(0, (x, y)- (y, x)).

Cu alte cuvinte putem anula fluxurile pe arcele în direcții opuse.

Astfel, deoarece este clar că valoarea fluxului maxim pentru orice orientare specificată a rețelei date nu este mai mare ca valoarea maximă a fluxului obținut prin înlocuirea fiecărui arc ne-direcționat printr-o pereche de arce direcționate, permițând ambele orientări pentru fiecare arc ne-direcționat, se rezolvă problema originală de maximizarea a lui v cu ajutorul ecuației (2.1) din capitolul I, constrângerile de capacitate pentru arcele direcționate (2.2) din capitolul I, și constrângerile (3.1) pentru arcele ne-direcționate.

4. Capacitățile nodurilor și alte extensii

Alte constrângeri de forma inegalităților, în plus față de limitarea fluxului pe arce se pot impune fără a modifica esența problemei maximizării fluxului. De exemplu să presupunem că fiecare nod x are o capacitate k(x) 0 , și ne propunem să găsim fluxul maxim de la s la t pentru capacitățile arcelor și nodurilor.

Mai explicit, să presupunem că toate arcele de intrare sunt direcționate de la intrare și toate arcele de ieșire sunt direcționate către ieșire, și se dorește să se maximizeze (s, N) cu

(4.1) (x, N) – (N, x)=0 xs, t,

(4.2) 0 (x, y) c(x, y) (x, y) A,

(4.3) (x, N)k(x), x t,

(N, t) k(t).

Această problemă poate fi redusă la cazul capacității arcurilor printr-un simplu artificiu. Se definește o noua rețea (N*, A*) pornind de la (N, A) după cum urmează. Pentru fiecare x N facem corespondența între două noduri x’ și x’’ ce aparțin lui N*; dacă (x, y) A, atunci (x’, y”) A*; în plus (x”, x’) A* pentru fiecare x N. Funcția capacității definita pe A* este

(4.5) c*(x’, y”)=c(x, y) (x, y) A,

(4.6) c*(x”, x’)=k(x) x N.

Astfel, de exemplu, dacă rețeaua (N,A) este cea din figura 4.1, rețeaua (N*,A*) este ilustrată în figura 4.2.

De fapt, fiecare nod x a fost împărțit în două părți, o parte “stângă“ x” și una “dreaptă” x’, astfel încât toate nodurile ce intră în x, acum, intră prin partea sa stângă, iar arcele care părăsesc x, acum, ies prin partea dreaptă .

Astfel orice funcție ce satisface(4.1)-(4.4), asta înseamnă, orice flux de la s al t în (N,A) care nu depășește capacitățile nodurilor, produce un flux echivalent * de la s” la t’ în (N*,A*) definind :

(4.7) *(x’, y”)= (x, y) x, y A,

(4.8) *(x”, x’)= (x, N) xt,

(4.9) *(t”, t’)= (N, t),

și invers.

Dacă noțiunea de mulțime deconectoare este extinsa să includă și noduri, la fel de bine ca și arce, teorema analoagă a teoremei lui Ford-Fulkerson spune că valoarea fluxului maxim este egală cu capacitatea mulțimii deconectoare de noduri și arce având capacitatea minimă.

În mod similar mai multe tipuri generale de constrângeri asupra fluxului ce intră sau iese din nodul x pot fi reduse la cazul capacităților arcelor prin extinderea rețelei. De exemplu, să presupunem că nodurile mulțimii A(x) sunt puse în submulțimi

A1(x),…, Am(x)(x)

cu condiția că

(4.11) Ai(x)Aj(x) Ai(x) Aj(x) sau Aj(x) Ai(x),

și presupunem, în plus la ecuațiile fluxului,

(4.12) (x, Ai(x))ki(x) i=1,…,m(x).

Constrângerile de forma (4.12), cu presupunerea (4.11), pot fi folosite cum se indică schematic în figura 4.3 și figura 4.4 pentru un singur nod x.

Constrângerile de acest tip asupra fluxurilor în x pot fi reduse la constrângeri asupra arcelor prin extinderea rețelei într-un mod analog.

De observat că inegalitățile (4.2), (4.3),(4.4) sunt cazuri speciale ale (4.12)

și ale constrângerilor similare asupra fluxului în x :

(4.13) (Bj(x), x) hj(x), j=1,…,n(x).

Dacă ne referim la fiecare mulțime (x, Ai(x)) și (Bj(x),x)) ca la mulțimi elementare de arce, și extindem noțiunea de mulțime deconectoare de arce, spunem că o colecție B de mulțimi elementare este o colecție deconectoare dacă fiecare lanț de la s la t are un arc în comun cu fiecare mulțime elementară conținută în B, se poate demonstra că fluxul maxim de la s la t este egal cu capacitatea minimă a blocajului (cu presupunerea (4.11)) și o presupunere asemănătoare asupra Bj(x)).

CAPITOLUL III

FLUX MINIM ÎN REȚELE

1.Noțiuni

Vom folosi următoarele notații: o rețea G=(X,U) cu funcția capacitate c, fluxul ƒ, intrarea x1=s și ieșirea xn=t.

Problema fluxului minim în rețele este analoagă cu cea a fluxului maxim, cu deosebirea că, condiția de mărginire devine :

(1.1) Pentru orice arc u al rețelei avem (u) c(u).

În acest caz se caută un flux astfel încât fluxul n la ieșirea rețelei să aibă cea mai mică valoare posibilă. Pentru această problemă vom modifica definiția tăieturii astfel : O tăietură este o mulțime de arce de forma ω-(A)(mulțimea de arce cu vârfurile finale în mulțimea A) , unde mulțimea de vârfuri A are proprietatea că xn A și ω+(A)=Ø. De exemplu, putem alege A={xn}.

Se observă că orice drum care leagă intrarea x1 cu ieșirea xn conține cel mult un arc dintr-o tăietură oarecare ω-(A), deoarece ω+(A)= Ø.

De aici și din condiția (1.1) deducem că pentru orice flux ƒ și orice tăietură ω-(A) există inegalitatea :

ƒn c(ω-(A)).

PROPRIETATEA 1.1. Fie µ un drum de la intrarea x1 la ieșirea xn. Dacă toate arcele acestui drum sunt nesaturate se poate mării fluxul ƒn în xn, cu respectarea condiției de conservare a fluxului și a condiției (1.1) .

În cazul fluxului minim, care trebuie să verifice condiția (1.1), proprietatea 1 rămâne valabilă, cu condiția că micșorăm fluxul pe fiecare arc al unui drum nesaturat μ cu δ*=. În acest fel fluxul ƒn va deveni ƒn-δ*<ƒn, iar cel puțin un arc al drumului μ va devenii saturat .

PROPRIETATEA 1.2 Fie v un lanț care unește intrarea x1 cu ieșirea xn. Vom nota cu v+ mulțimea arcelor lui v orientate în același sens cu sensul de parcurgere al lanțului v de la x1 la xn, iar prin v- mulțimea arcelor lui v orientate în sens invers cu sensul de parcurgere al lanțului v de la x1 la xn .Vom nota cu δ*=, și vom micșora fluxul cu δ* pe fiecare arc u v+ și-l vom mări cu δ* pe fiecare arc uv- .

În acest fel vom obține un flux cu componente ne-negative care verifică condiția (1.1) și condiția de conservare a fluxului, astfel încât fluxul la ieșire va avea o valoare egală cu ƒn-δ*<ƒn.

Intr-adevăr, deoarece mărim fluxul pe arcele u v-, nu mai trebuie să impunem nici o condiție componentelor fluxului pe aceste arce.

Caracterizarea fluxului minim se face acum analog cu fluxul maxim, prin inexistența lanțurilor nesaturate de al intrare la ieșire (pentru care δ*>0). Demonstrația acestei proprietăți rezultă din demonstrația valabilități algoritmului Ford-Fulkerson transpus pentru fluxuri minime.

2. Algoritmul lui Ford-Fulkerson

Etapa1. Obținerea uni flux compatibil.

Se alege un flux care astfel ca φ(u)c(u) pentru orice arc u U, cu respectarea condiției de conservare a fluxului în fiecare nod al rețelei. Pentru aceasta se pot considera diferite drumuri de la intrare la ieșire, pe care se definește un flux superior capacităților tuturor arcelor.

Etapa2. Obținerea unui flux complet.

Se diminuează fluxul pe arcele drumurilor de la x1 la xn, astfel încât fiecare drum să conțină cel puțin un arc saturat.

Etapa3. Obținerea unui flux minim în xn.

Se vor determina lanțurilor nesaturate de la x1 la xn poate fi micșorat, folosind următorul procedeu de etichetare:

Se marchează x1 cu semnul -.

Un vârf fiind marcat, se va marca :

cu [-xi] orice vârf xj nemarcat anterior, cu proprietatea că arcul u=(xi,xj) este nesaturat, deci φ(u)>c(u);

cu [+xi] orice vârf xj ne-marcat cu proprietatea că există arcul (xj,xi) în rețea.

Dacă prin acest procedeu de etichetare se marchează ieșirea xn, atunci ƒn poate fi micșorat cu δ* relativ la lanțul nesaturat v, format din vârfuri etichetate, care unește intrarea cu ieșirea.

Pentru aceasta vom micșora fluxul cu δ* pe fiecare arc u v+ și îl vom mări cu δ* pe fiecare arc u v-, folosind notațiile introduse anterior.

Se repetă aplicarea acestei metode de etichetare până când nu va mai fi posibil să se marcheze ieșirea rețelei, adică până când nu vor mai exista lanțuri nesaturate care să permită micșorarea fluxului în xn. In acest moment ne oprim, deoarece fluxul obținut este minim, iar mulțimea arcelor care unesc vârfurile marcate cu vârfurile nemarcate constituie o tăietură cu capacitatea maximă, egală cu ƒn.

Intr-adevăr, să notăm cu A mulțimea vârfurilor care nu pot fi etichetate prin procedeul descris. Vârful xn ne putând fi etichetate, rezultă că xn A. Obținem de asemenea că ω+(A)=0, deoarece dacă un arc (xi,xj) ω+(A) rezultă că xi A și xj A. Dar xi fiind etichetat și existând arcul (xi,xj) rezultă că și xj poate fi etichetat, deci xjA, ceea ce este contradictoriu cu ipoteza făcută. Deci ω-(A) constituie o tăietură și pentru orice arc u ω-(A) avem ƒ(u)=c(u), deoarece în caz contrar și extremitatea terminală a acestui arc, care aparține mulțimii A poate fi etichetată, ceea ce contrazice definiția mulțimii A. Deci putem scrie:

deoarece ω+(A)=0.

Însă pentru orice flux ƒ și orice tăietură ω-(A) există inegalitatea ƒnc(ω-(A)), deci fluxul ƒn este minim, iar tăietura definită de A are o capacitate maximă.

Deci inexistența lanțurilor nesaturate de la x1 la xn în rețea are drept consecință minimalitatea fluxului ƒn. Faptul că algoritmul lui Ford-Fulkerson pentru flux minim are număr finit de pași se justifică în mod analog cu cazul fluxului maxim.

De aici mai rezultă că teorema lui Ford-Fulkerson în cazul fluxului minim se poate enunța astfel:

Intr-o rețea de transport valoarea minimă a fluxului la ieșire este egală cu capacitatea maximă a unei tăieturi, adică:

min ƒn=max c(ω-(A)).

` A|xn A, ω+(A)=

3.Exemplu.

Să aplicăm algoritmul lui Ford-Fulkerson pentru a găsii fluxul minim în rețeaua din fig 3.1, unde am reprezentat un flux complet pe arcele rețelei. Arcele saturate au fost desenate îngroșat.

Etichetăm vârfurile, reușind să marcăm ieșirea x6 de-a lungul lanțului [x1, x2, x3, x5, x6], deci fluxul nu este minim. δ*=min(9-4,8-6,9-8)=1, fluxul va fi micșorat cu o unitate pe arcele (x1, x2), (x3, x5), (x5, x6) și va fi mărit pe arcul (x3, x2) care va deveni saturat. Noul flux este reprezentat în fig. 3.2.

Și pentru acest flux ieșirea x6 poate fi marcată pe lanțul [x1, x2 ,x3, x5, x4, x6] cu δ*=min (8-4, 7-6, 6-5), deci fluxul va fi diminuat cu o unitate pe arcele (x1,x2),(x3,x5),(x4,x6) și va fi mărit cu o uitate pe arcele (x3, x2) și (x4, x5), obținându-se fluxul din fig. 3.3. Acest flux este minim, deoarece nu mai putem marca ieșirea x6.

Mulțimea vârfurilor nemarcate este A={x4, x5, x6}, deci tăietura de capacitate maximă este:

ω-(A)={ (x2, x4), (x3, x5)}

Se verifică ușor că ω+(A)= și c(ω-(A))=13=ƒ6

CAPITOLUL IV

FLUX DE COST MINIM DE LA s LA t

În capitolul I am considerat problema maximizării fluxului de la s la t fără a ne referi la nici un cost. Vom considera acum problema găsirii unui flux de la s la t de o valoare dată v astfel încât costul fluxului este minimizat. În această problemă, fiecare arc are două numere asociate, capacitatea și costul pe unitatea de flux de-a lungul arcului de valoare .

Evident, dacă v este luat mai mare decât valoarea fluxului maxim de la s la t nu există nici o soluție. Oricum, dacă v este luat mai mic sau egal cu această valoare un număr de fluxuri diferite vor fi, în general, posibile și ce se cere este să se găsească acel flux de valoare v și care are costul minim. Cea mai cunoscută procedură pentru problema costului minim este așa-numita „out-of-kilter” a lui Ford și Fukerson. Algoritmii pe care îi voi enumera sunt mai simplii decât metoda „out-of-kilter” și folosesc metode care au fost deja prezentate. Acești algoritmi sunt cei ai lui Klein, și Busacker și Gowen.

1. Un algoritm bazat pe determinarea circuitelor negative

Să presupunem că un flux posibil de valoare v există în graf și acest flux este cunoscut. Un asemenea flux poate fi obținut aplicând algoritmul fluxului maxim de la (s la t) și mărind fluxul pe lanțurile corespunzătoare (flow-augmentation-chains) cu un flux nu până când maximul este atins ci până când fluxul ia valoarea v.

Cu acest flux posibil, definim un nou graf incrementat , în același mod cum a fost explicat în secțiunea I.8. și cu costurile arcelor specificate astfel:

Pentru orice arc costul .

Pentru orice arc costul .

Noul graf reprezintă acum capacitățile incrementate și costurile (relative la fluxul inițial ) oricărui alt flux care urmează să fie introduse în G. Algoritmul se bazează pe următoarea teoremă:

TEOREMA 1.1. este flux de cost minim de valoare v dacă și numai dacă nu există nici un circuit în astfel încât suma costurilor de pe fiecare arc din este negativă.

Demonstrație. Fie costul fluxului în graful G și suma costurilor arcelor în circuitul al grafului .

Necesitatea. Fie pentru unele circuite din . Adăugarea unei unități de flux în circuitul duce la un nou flux și lasă valoarea v a fluxului de la s la t neschimbată. Costul fluxului este ceea ce contrazice presupunerea că este fluxul de cost minim de valoare v.

Suficiența. Presupunem că pentru orice circuit din graful și că este fluxul de cost minim de valoare v.

Să scriem acum pentru fluxul în care fluxul pe arcul este .

Din moment ce și pot fi scrise ca sumă de fluxuri pe drumurile de la s la t în graful G, construcția grafului unitar pentru fluxul duce la următoarele grade ale vârfurilor:

.

Astfel, este format dintr-o mulțime de ,,conformal” unități de fluxuri pe circuit în circuitele și putem scrie:

Deoarece fluxurile sunt și ele „conformal” și știm că fluxul este posibil, orice sumă există pentru orice . Astfel, considerând fluxul avem:

.

Vom considera acum graful incrementat . Singurele arce ale acestui graf care au costurile reduse în comparație cu costurile corespunzătoare în graful sunt arcele „ de întoarcere” din . Oricum, deoarece fluxurile sunt „conformal”, astfel de arce nu pot fi niciodată folosite de circuitele rămase și deci devin irelevante pentru observația următoare.

Atunci avem:

Pentru orice .

Costul fluxului este :

Continuând în același fel obținem care contrazice presupunerea că este fluxul de cost minim. Deci am demonstrat teorema.

q.e.d.

Astfel, conform teoremei 1.1, tot ceea ce este necesar pentru a găsi un flux de cost minim de valoare v în G este să pornim cu un flux posibil de valoare v, să formăm graful și să-l verificăm, pentru circuitele de cost negativ folosind orice algoritm de găsire a celui mai scurt drum. Dacă nu există nici un circuit de cost negativ fluxul este unul de cost minim. Dacă există un circuit de cost negativ, găsim acest circuit și transmitem fluxul maxim posibil de-a lungul circuitului. Fluxul total de la s la t rămâne astfel neschimbat la valoarea v, cu toate că costul lui a fost redus cu unde este costul negativ al circuitului . Evident, δ trebuie ales astfel încât capacitățile arcelor din să nu fie schimbate, adică:

(1.1)

Din cauza alegerii inițiale a capacităților arcelor din ; când acest flux este adăugat fluxului deja existent în G, noul flux rezultat este și el posibil. Procesul poate fi repetat prin începerea cu acest nou flux formând un nou graf relativ la noul flux și verificând circuitele de cost negativ din nou.

DESCRIEREA ALGORITMULUI

Pas1. Folosim algoritmul de flux maxim de la s la t pentru a determina un flux posibil de valoare v în graful G.

Pas2. Relativ la acest flux formăm graful conform regulilor date mai sus.

Pas 3. Cu matricea costurilor a grafului ca punct de plecare, folosim un algoritm de găsire a celui mai scurt drum pentru a determina dacă există un circuit de cost negativ în . Dacă un asemenea circuit există, identificăm circuitul de cost negativ și mergem la pasul 5.

Dacă nu există nici un astfel de circuit, atunci ne oprim. Fluxul curent ξ este unul de cost minim .

Pas 4. Calculăm δ conform ecuației (1.1)

Pentru toate (μ,xjμ ) din Φ cu cijμ <0 schimbăm fluxul ji al arcului corespunzător (xj,xi) din G de la ji la ji-δ .

Pentru toate (μ,xjμ ) din Φ cu cijμ >0 schimbăm fluxul ij al arcului corespunzător (xi,xj) din G de la ji la ij+δ .

Pas5. Cu acest nou flux ne întoarcem la pasul 2.

1.2. Exemplu.

Considerăm graful G ilustrat în figura 1.1 de mai jos, unde primul număr din eticheta fiecărui arc este capacitatea și cel de al doilea număr este costul. Vrem să găsim fluxul de cost minim de valoare 20 de la s la t. Vom folosi algoritmul lui Floyd de găsire a celui mai scurt drum pentru a determina circuitele de cost negativ de la pasul 3 cu metoda de mai sus.

Pas1. Algoritmul fluxului maxim ne dă primul flux posibil cum se vede și în figura 1.2(a). Costul acestui flux este :

16(7+25+5)+4(28+7)=732.

Pas2. Relativ la aceste flux formăm graful Gμ () ca în figura 1.2(b), unde arcele de cost negativ sunt arătate punctate.

Pas3. Pornim cu matricea costurilor :

(unde intrările libere sunt luate ca infinite ) și aplicând algoritmul lui Floyd, sunt obținute următoarele matrici de cost minim cu matricile drum asociate lor:

În timpul acestui ultime iterații ck 4,4 devine negativ cu valoarea –15 care indică existența unui circuit de cost negativ care conține vârful x4. Acest circuit e găsit din matricea drum ca fiind (x4,x3,x2,x4)

Pas4. Ecuația (1.1) dă valoarea lui δ astfel :

δ=min[12, 16, 18]=12

(x4,x3) (x3,x2) (x2,x4)

Noul flux mărit cu δ este introdus în circuit, este arătat în figura 1.2(c). Costul acestui nou flux este 552.

Întorcându-ne la pasul 2, noul graf Gμ () este găsit și ilustrat în figura 1.2(d).

Procedând în același mod ca mai sus obținem:

Pas3. Se găsește circuitul de cost negativ –10 (x6,x1,x4,x6)

Pas4. δ =min[4,11,19]=4

Noul flux de cost 512 este arătat în figura 1.2(e).

Pas2. Graful Gμ ( ) relativ la noul flux este acum ilustrat în figura 1.2(f).

Pas3. Se găsește circuitul de cost negativ (x7,x3,x2,x5,x7) cu costul –8.

Pas4. δ=min[16,4,16,16]=4

Noul flux de cost 480 e ilustrat în figura 1.2(g)

Pas2. Graful Gμ () devine cel din figura 1.2(h)

Pas3. Se găsește circuitul de cost negativ –4 (x1,x4,x6,x7,x5,x2,x1)

Pas4. δ=min[7,15,1,4,4,16]=1

Noul flux de cost 476 e ilustrat în figura 1.2(i)

Pas2. Graful Gμ () este cel din figura 1.2(j)

Pas3. Se găsește circuitul de cost negativ –2 (x1,x2,x4,x1).

Pas4. δ=min[1,6,5]=1

Noul flux de cost 474 este arătat în figura 1.2(k)

Pot fi găsite acum circuite de cost ne-negativ în graful incrementat astfel încât fluxul arătat în figura 1.2(k) este de cost minim și anume costul 474 și valoarea 20.

1.3 Pasul 3 al algoritmului din 1.1.

În exemplul de mai sus s-a folosit metoda lui Floyd pentru a găsii circuite de cost negativ în graful de cost incrementat Gμ () la pasul 3 al algoritmului de aflare a fluxului de cost minim dat în 5.1.1. În orice caz, aceasta nu este cea mai bună metodă de a determina circuite de cost negativ într-un graf în care există un vârf x0 din care putem ajunge la toate celelalte vârfuri ale lui G. O metodă mai bună este de a folosi un algoritm care găsește cele mai mici drumuri de la x0 la celelalte vârfuri, decât să folosi algoritmul lui Floyd care găsește cele mai scurte drumuri între orice perechi de vârfuri.

Pentru graful incrementat Gμ () este chiar ușor de arătat că există întotdeauna cel puțin un vârf din care pot ajunge în toate celelalte vârfuri ale grafului Gμ (), și chiar vârful terminal are această proprietate. Aceasta se arată astfel :

Deoarece în graful incrementat Gμ () există un arc (μ,xiμ ) pentru fiecare arc (xj,xi) din G, arc al cărui flux este diferit de zero, toate vârfurile xμ i din Gμ () corespunzătoare vârfurilor xi din G care se găsesc pe drumurile de la s la t, pot fi atinse din t folosind drumurile de întoarcere formate din arcele (μ,xiμ ). În acest fel intrarea s poate fi atinsă. Acum toate vârfurile xi din G pot fi atinse din s; (altfel xi poate fi scos din G fără nici un efect asupra fluxului). Astfel, deoarece, aceste arce (xi,xj) nu duc nici un flux în G apar de asemenea și ca arce (μ,xjμ ) în Gμ (), este evident că aceste vârfuri xiμ din Gμ () corespunzătoare vârfurilor xi din G care nu se găsesc pe drumurile pe care trece fluxul, pot fi atinse din t via s; adică prima dată atingând s cum am menționat mai sus și apoi urmărind un drum de la s la xiμ .

Astfel în graful incrementat Gμ (), toate vârfurile pot fi atinse din t și dacă acest vârf este folosit ca vârf de intrare în calculul celui mai scurt drum de la t la toate celelalte vârfuri ale lui Gμ (), circuitele de cost negativ din Gμ () pot fi găsite.

Folosind o asemenea abordare pentru a aplica pasul 3 al algoritmului de aflare a fluxului de cost minim, Bennington a afirmat că acest algoritm este cel puțin la fel de bun ca algoritmul “out -of-kilter”.

Pentru grafuri cu n vârfuri și m arce s-a observat, făcându-se teste, că timpul de calcul T al algoritmului este:

T= -23+00113n+000166m(sec IBM 360/75)

Pentru un graf cu 200 vârfuri și 5000 arce acest timp este de 8 sec.

2.Algoritmul de determinare a drumului cu flux de cost minim

Algoritmul din paragraful 1. începe cu un flux arbitrar de valoare v și continuă cu îmbunătățirea fluxului până când fluxul de cost minim * s-a obținut. În termenii programării matematice acest algoritm se numește primal, deoarece prima operație e de obținere a unui flux posibil și apoi îmbunătățirea lui în timp ce se menține fiabilitatea. O altă alternativă de abordare este metoda duală, care pentru această problemă, constă în construirea fluxului de cost minim care are o valoare v0<v și adăugând flux pe rețea se obține un nou flux de cost minim cu valoarea v1>v0 etc. până când fluxul de cost minim este găsit.

De observat că un flux de cost minim este întotdeauna posibil din moment ce fluxul zero este fluxul de cost minim de valoare zero.

Algoritmul care urmează este bazat pe găsirea drumului cel mai scurt și pe următoarea teoremă:

Teorema 2.1: Dacă este un flux de cost minim într-un graf G având valoarea v și P* este drumul cel mai scurt (de cost minim) de la s la t în graful incrementat Gμ (), atunci +1(P*) este fluxul de cost minim de valoare v+1.

Demonstrația implică faptul că dacă Gμ () nu conține circuite de cost negativ, atunci Gμ (+1(P*)) de asemenea nu conține astfel de circuite. Rezultatul reiese direct din teorema 1.1.

2.1 Descrierea algoritmului

Pas1. Începem, cu toate fluxurile arcelor egale cu zero și valoarea fluxului zero.

Pas2. Construim graful incrementat Gμ ()=(Nμ , Aμ 1 Aμ 2) și atribuim costuri arcelor astfel :

Pentru orice arc (μ, xjμ ) Aμ 1 luăm cμ ij=c ij

Pentru orice arc (μ, μ) Aμ 2 luăm cμ ji=-c ij

Pas3. Găsim drumul cel mai scurt P* în Gμ () de la vârful s la t.

Pas4. Calculăm cea mai mare valoare δ a fluxului ce poate fi transmisă de-a lungul lui P* înainte de-a schimba structura lui Gμ (), δ fiind dat de :

δ =min [qμ ij]

(xμ i,xμ j)P*

Pas5. (i) Dacă valoarea fluxului +δ(P*) este mai mică decât valoarea v, modificăm cu +δ(P*) și ne întoarcem la pasul 2;

Dacă valoarea fluxului +δ(P*)= v, stop. +δ(P*) este fluxul de cost minim căutat.

(iii) Dacă valoarea +δ(P*) =h>v, ne oprim , +(δ-h+v)(P*) este fluxul minim căutat.

Este important să observăm că graful Gμ () la pasul 2 conține atât arce cu costuri pozitive cât și arce cu costuri negative, și deci algoritmul de determinare a celui mai scurt drum folosit la pasul 3 nu poate fi cel dat de metoda Dijkastra. Oricum, Edmonds și Karp au descris recent o metodă care depășește dificultățile de mai sus și permite folosirea unui algoritm mai eficient de determinare a celui mai scurt drum .

2.2 Exemplu.

Să recalculăm fluxul de cost minim de valoare 20 pentru graful din figura 1.1.

Inițial luăm =0. Graful incrementat Gμ () este atunci ca cel ilustrat în figura 1.1. Drumul cel mai scurt în acest graf este P*1=(x1,x2,x4,x3,x7) de cost 22 și δ este calculat ca fiind 12.

Fluxul devine acum 12 (P*1). Drumul cel mai scurt în graful incremental corespunzător este P*2=( x1,x2,x4,x6,x7) de cost 23 și δ este calculat să fie 4.

Fluxul devine acum 12 (P*1)+4 (P*2). Drumul cel mai scurt în Gμ () este P*3=(x1,x4,x6,x7) de cost 25 și δ este 1.

Fluxul devine 12 (P*1)+4 (P*2)+1 (P*3). Drumul cel mai scurt în Gμ () este P*4=(x1,x4,x2,x5,x7) de cost 31 și de-a lungul căruia cele 3 unități de flux rămase pot fi transmise pentru a rezulta un flux de cost minim ca în fig. 1.2 (k).

CAPITOLUL V

FLUXURI ÎN GRAFURI CU CÂȘTIGURI

1.Introducere

Până acum, am presupus că fluxul ce intră într-un arc este egal cu fluxul ce părăsește arcul respectiv. În anumite situații practice, aceasta nu este o presupunere corectă. De exemplu, în rețelele de conducte ce transportă lichide sau rețelele de fire ce transportă curent electric, scurgerile din sistem, implică tot o pierdere de flux pe arcul ce reprezintă ruta. În procesul de producție, ce poate fi reprezentat ca un graf, arcele reprezentând operații, valoarea materialelor ce părăsesc un arc este mai mare decât valoarea materialelor ce intră în acel arc, adică, este un câștig ce reprezintă valoarea adăugată de operație. În problema schimbului de bunuri ( ex. Vânzarea și cumpărarea de valută), câștigurile pe arce sunt câștiguri reprezentând valoarea ratei de schimb care convertește fluxul de intrare (măsurat într-o monedă) în fluxul de ieșire (măsurat într-o altă monedă).

În acest capitol vom studia problema găsirii fluxului maxim de la s la t într-un graf cu câștiguri ne-negative arbitrare gij și capacitățile qij asociate cu arcele (xi, xj) ale grafului G. Problema este analoagă cu problema fluxului maxim de la s la t; cu toate că acum fluxurile de intrare și de ieșire nu au legătură decât prin graful G care este capabil atât să “absoarbă” cat și să “genereze” flux.

Dacă notăm eij ca fluxul de intrare într-un arc (xi, xj) și 0ij ca fluxul de ieșire din acel arc avem :

(1.1) 0ij=gijeij

O să presupunem în continuare că, capacitățile arcelor se referă la fluxurile de intrare, astfel că pentru orice arc avem :

(1.2) eijqij

fără a ține cont de valoarea lui 0ij . Dacă notăm fluxul de intrare în s cu vs și fluxul de ieșire din t cu vt, putem spune că un flux Ξ=(e, 0) este posibil dacă satisface condițiile de continuitate a fluxului în vârfuri, adică :

vs, pentru xi =s

(1.3) -= -vt, pentru xi =t

0, pentru xi s,t

și de asemenea condițiile (1.1) și (1.2) pentru orice arc (xi, xj) din G.

Vom da acum două definiții :

Definiție. Un flux posibil =(e, 0)se spune că e maxim dacă determină cea mai mare valoarea vt (sau ) dintre toate fluxurile posibile.

Definiție. Un flux posibil =(,) se numește optim dacă pentru orice alt flux posibil Ξ :

Sau : , când

Sau: , când .

unde și sunt fluxurile de intrare și de ieșire corespunzătoare lui .

Aceste ultime condiții corespund conceptului intuitiv de optimalitate acela că : și sunt cele mai mari posibile; sau și sunt cele mai mici posibile.

Definiție. Un flux posibil se spune că este optim-maximal dacă este flux optim și maxim.

O să ilustrăm definiția de mai sus cu un exemplu. Să considerăm graful din fig 1.1(a) unde prima etichetă de pe arc este capacitatea și cea de-a doua este câștigul.

Atunci

Fluxul ilustrat în fig 1.1(b) este fluxul maxim de valoare =18 și =6;

Fluxul ilustrat în fig. 1.1 (c ) este un flux optim de valoare =3 și =0 (De observat că fluxul este un flux de trecere printr-un circuit a cărui câștig total este mai mare ca 1. De observat și că >și deci acesta nu este un flux maxim, oricum, este maximul ce poate fi obținut cu =0);

Fluxul ilustrat în fig. 1.1 (d) este un flux optim-maximal având =, dar =5 <=6 , și de fapt, după cum vom vedea mai târziu, valoarea 5 este cea mai mică valoare posibilă a lui pentru a produce un flux la ieșire de valoare 18.

2. Augmenting chains

Să considerăm un graf G cu câștiguri și un flux existent posibil =(,), ce trece prin acesta. Vom nota asta cu G(Ξ). Un lanț (nu neapărat simplu) de arce de la vârful la vârful se numește augmenting chain de la la dacă fluxul poate fi transmis în G(Ξ) de-a lungul lanțului de la la (Acesta este analoaga definiției unui flow augmenting chain de la s la t definit pentru problema fluxului maxim de la s la t ). Dacă lanțul este dat de secvența de vârfuri ,,…, , atunci fie F mulțimea tuturor arcelor de înaintare în acest lanț, adică arcele (,) cu , și fie B mulțimea tuturor arcelor de întoarcere, adică, acelea cu . Un lanț este atunci augmenting dacă pentru orice arc de înaintare (xi,xj) F avem eij<qij și pentru orice arc de întoarcere (xj,xi) B avem eji>0

Câștigul lanțului

Câștigul unui lanț S=,,…,este dat de :

(2.1) g(S)=

B. Capacitatea lanțului

Capacitatea incrementată a unui lanț augmenting S este fluxul maxim de intrare în care poate fi transmis de-a lungul lanțului la , până la nivelul când, ori fluxul în unele arce de înaintare ale lui S este saturat, ori fluxul în unele arce de întoarcere devine zero.

Dacă S este un lanț simplu, și un flux δ intră în , atunci fluxul ce intră în în arcul (,) din S este:

(2.2) ip+1 =

= δ g(Sp)

unde Fp și Bp sunt respectiv arcele de înaintare și de întoarcere ale sub-lanțului Sp=,,…,și g(SP) este câștigul lui Sp. Dacă (,) este un arc de înaintare din S având fluxul ip+1, arcul va devenii saturat atunci când ip+1 + ip+1 =qip,ip+1.

Dacă este un arc de întoarcere cu fluxul ip , valoarea fluxului va fi redusă la zero când ip+1=ip, adică, atunci când ip+1=ip ip .Capacitatea incrementată a lanțului S este atunci dată de:

(2.3)

Dacă S nu este un lanț simplu și unele arce apar de mai multe ori, o expresie similară cu (2.3) poate fi obținută facil.

Pentru lanțul S din figura 2.1(a) și valoarea fluxului inițial dată, mărirea cu fluxul δ în x1, este cea ilustrată în fig 2.1(b). Valoarea maximă a δ care lasă fluxul posibil este atunci q(S)=0.6. Pentru această valoare fluxul în arcul (x4,x3) este redus la zero, adică S încetează a mai fi un lanț augmenting în noul G(Ξ). Luând fluxul inițial ce intră în arcul (x4,x3), să zicem 8, în loc de 2, valoarea maximă posibilă a lui δ ar fi fost 2.1, moment în care arcul (x4,x5) din S devine saturat.

Pentru lanțul S care nu este simplu , cu fluxul inițial ilustrat în fig. 2.1( c), creșterea fluxului cu δ în x1 este ilustrat în fig.2.1(d) . Capacitatea incrementată a acestui lanț este atunci , moment în care (x3, x4) devine saturat.

3.Cicluri active

Deoarece un ciclu poate fi considerat ca un lanț cu vârful inițial și final identice, câștigul unui ciclu (și capacitățile sale), pot fi definite în aceeași manieră ca cel ale unui lanț.

Un ciclu Φ se spune că este activ în G(Ξ) referitor la vârful t dacă :

(i) Câștigul său este mai mare decât unitatea;

(ii) Capacitatea incrementată este diferită de zero și

(iii) Sunt anumite vârfuri xi în Φ, astfel că există un lanț augmenting de la xi la t.

Un ciclu activ referitor la nodul inițial s poate fi definit similar . Din definiția de mai sus, ar trebui să fie clar că prin transmiterea unui flux printr-un ciclu activ, se poate crea extra-flux ,din proprietatea (i), și acest extra-flux poate fi transmis până la t, din proprietatea (iii). În exemplul din fig.1.1 ( c) dat mai sus, fluxul a fost creat prin trecerea de-a lungul ciclului activ (x4,x2,x3,x4).

Un ciclu activ, referitor la t, se spune că este de-activat dacă flux adițional este impus în graful G, astfel încât, ori capacitatea sa incrementată este redusă la zero, sau capacitățile tuturor lanțurilor augmenting de la orice vârf de pe ciclu la t sunt reduse la zero(adică, nu mai există augmenting în noul G(Ξ)).

Teorema 3.1. Un flux este optim dacă și numai dacă G() nu conține nici un ciclu activ de la s la t.

Teorema 3.2. Dacă este un flux optim, atunci dacă fluxul este majorat de la s la t de-a lungul lanțului augmenting cu cel mai mare câștig, fluxul rezultat este de asemenea optim.

Teorema 3.3. Un flux este optim-maximal dacă unele tăieturi (X0,X-X0) ce separă s de t sunt saturate și nu există nici un ciclu activ ce trece prin t cu toate vârfurile sale în X-X0.

4. Algoritmul aflării fluxului optim pentru grafuri cu câștiguri

Din teoremele de mai sus, optimalitatea algoritmului rezultă imediat :

Pas1. Începem cu orice flux posibil Ξ din G (Fluxul zero în toate arcele, este acceptat);

Pas2. Găsim un ciclu activ Φ în G(Ξ), ce trece prin t;

Pas3. Fie xi un vârf din Φ astfel încât lanțul augmenting este de la xi la t (Observăm că xi poate fi chiar t). Pornind de la xi transmitem un flux δ prin ciclul activ și apoi transmitem excesul de flux la xi , de-a lungul lanțului augmenting la t. Alegem δ astfel încât împreună cu fluxul constant existent Ξ, ori capacitatea incrementată a Φ, ori a lanțului augmenting sunt reduse la zero.

Pas4. Majorăm Ξ și ne întoarcem la pasul 2 până când toate ciclurile active sunt de-activate și nu mai este găsit nici un ciclu activ, în care caz mergem la pasul 5 (La acest stadiu Ξ este fluxul optim cu =0).

Pas5. Găsim lanțul augmenting de la s la t cu cel mai mare câștig. Transmitem flux pe acest lanț până când capacitatea incrementată este redusă la zero.

Pas6. Majorăm Ξ și repetăm pasul 5 până când fluxul de ieșire este cel de valoarea cerută de fluxul optim, ori până când nici un alt lanț augmenting poate fi găsit, caz în care fluxul este fuxul optim-maximal .

Pașii algoritmului de mai sus sunt foarte simpli și această metodă este eficientă. Pașii 2 și 5 pot , încă o dată, să fie realizați prin mijloacele unui algoritm de determinare a celui mai scurt drum. Astfel, corespunzător grafului G(Ξ) să definim graful incrementat Gμ (Ξ)=(Xμ , Aμ ) cu vârfurile Xμ =X și arcele Aμ astfel încât:

(xμ i,xμ j) Aμ , dacă 0

cu “costul” incrementat:

cμ ij=-log(gij)

și capacitatea:

= qij-

și

(xμ j,xμ i) Aμ , dacă 0

cu “costul” incremental

cμ ji = -log(1/gij)

și capacitatea :

=

Un ciclu Φ în G(Ξ) cu câștig mai mare decât cel unitar corespunde unui circuit din Gμ (Ξ) cu “cost” negativ. Acesta poate fi văzută prin logaritmarea ambilor membrii ai ecuației (2.1) corespunzător unui ciclu Φ.

Astfel:

log[g(Φ)]=] , unde F și B sunt mulțimile arcelor de înaintare și respectiv de întoarcere din ciclul Φ.

Dacă g(Φ)>1 atunci log[g(Φ)]>0 ceea ce implică că, costul ciclului Φ din Gμ (Ξ), adică , trebuie să fie negativ. Invers, dacă g(Φ)1 costul lui Φ din G(Ξ) este ne-negativ.

Astfel, ciclurile active din G(Φ)- la pasul 2 al algoritmului de mai sus -pot fi determinate prin încercarea de găsii toate drumurile cele mai scurte (de cost cel mai mic) de al vârfurile lui Gμ (Ξ) la vârful terminal t, și să testăm dacă există circuitele de cost negativ . Oricum, dacă fluxul δ este transmis prin ciclul activ Φ la pasul 3 și apoi transmis prin lanțul augmenting la t, nu reduce capacitatea lui Φ la zero, dar în schimb reduce la 0 capacitatea lanțului augmenting, atunci la următoarea execuție a pasului 2 este necesar doar să găsim un alt lanț augmenting de la un vârf al lui Φ la t. Un astfel de lanț, ar transforma Φ în ciclul activ și se poate continua cu pasul 3, etc., până când Φ este de-activat și unele cicluri active diferite trebuie să fie calculate la pasul 2. Acest graf nu conține circuite de cost negativ dacă primii 4 pași ai algoritmului au fost executați.

5.Exemplu

Când dorim să găsim fluxul optim-maximal de la vârful x1 la x8 în graful din

fig.5.1. unde prima etichetă a arcului este capacitatea sa, iar a doua reprezintă câștigul.

Începând cu Ξ =(0,0), primul ciclu activ găsit este Φ=( x5,x4,x2,x5) cu lanțul augmenting (x5,x8). Transmitem unui flux δ (unde δ este flux de intrare al arcului (x5,x4)) de-a lungul acestui circuit, ca în fig.5.1, are ca rezultat o valoare maximă posibilă a lui δ de unități, și pentru această valoare fluxul rezultat este ilustrat (cu numere subliniate), în fig. 5.2(a)- unde arcul (x5,x8) este saturat. Ciclul Φ nu este redus la capacitatea zero, astfel că la următoarea iterație, când algoritmul celui mai scurt drum (de la celelalte vârfuri din Gμ (Ξ) la vârful t), etichetează vârful x4 din Φ; Φ devine activ cu acest nou drum de flux augmenting (x4,x6,x7,x8).

Transmițând fluxul δ de-a lungul acestui ciclu și transmițându-l de-a lungul drumului augmenting la t, ca în figura 5.2(a) produce fluxul arătat subliniat în fig. 5.2(b)

Un nou ciclu activ (x8,x5,x4,x6 ,x7,x8) este acum determinat la pasul 2 și transmiterea fluxului δ prin acest ciclu, ca în figura 5.2(b) produce fluxul ilustrat subliniat în fig.5.2( c). În sfârșit ciclul activ (x8,x5,x2,x4,x6,x7,x8) este determinat, și de-activarea sa prin transmiterea fluxului conduce la fluxul din fig.5.2(d) care este fluxul optim, din moment ce nici un alt ciclu activ nu mai poate fi găsit.

Lanțul augmenting de al s la t de câștigul cel mai mare este acum (x1,x4,x2,x5,x8) de capacitatea 1/6. Odată ce acest lanț este saturat (arcul (x4,x2) este saturat), lanțul augmenting cu al doilea cel mai mare câștig este (x1,x2,x5,x8) care când este saturat determină fluxul din fig.5.2(e) care este fluxul optim-maximal căutat din moment ce nici un drum augmenting de la s la t nu mai poate fi găsit

6. Grafuri cu câștiguri ale vârfurilor

In paragraful II.4. problema fluxului maxim de la s la t cu capacitățile vârfuri a fost rezolvată prin simpla înlocuire a fiecărui vârf xj printr-o pereche de vârfuri x+j și x-j. În mod similar, dacă vârfurile unui garf G au asociate câștiguri astfel încât condițiile de continuitate (1.3) nu sunt satisfăcute, putem forma un alt graf G0 prin înlocuirea fiecărui vârf xj din G cu o pereche de vârfuri x+j și x-j cu un arc (x+j ,x-j) între ele; câștigul acestui arc este egal cu câștigul vârfului xj. Pentru un arc (xi, xj) din G vom avea un arc (x-i, x+j) în G0 și pentru un arc (xj, xk) din G vom avea un arc (x-j, x+k) în G0. Problema devine acum una de găsire a fluxului optim în graful G0 având doar câștiguri pe arce.

CAPITOLUL VI

APLICAȚII

Acest capitol își propune să dea o implementare în limbajul Pascal a problemei de flux maxim prezentată în capitolul I și a problemei fluxului minim prezentată în capitolul III, folosind algoritmul lui Ford-Fulkerson. În timp acești algoritmi au fost îmbunătățiți de către Edmonds și Karp, Dinitz, Goldberg și Tarjan. Vor fi prezentați acești algoritmi deoarece ei stau la baza rezolvării problemelor din celelalte capitole.

1.Problema fluxului maxim

Fie G=(X,U) o rețea. Pentru fiecare arc avem atașate capacitate c și fluxul g. Problema fluxului maxim constă în determinarea unui flux g astfel încât fluxul la ieșire(suma fluxurilor pe arcele ce intră în ieșire) Vg să fie maxim.

Ne punem deci problema ca pornind de la un flux g într-o rețea să mărim acest flux până când el atinge o valoarea maximă. Vom considera c,g:UN.

Este clar că dacă pentru un arc u U, g(u)=c(u), fluxul pe acel arc nu poate fi mărit. Un astfel de arc se numește saturat. Pe arcele nesaturate vom mări fluxul astfel:

Pentru arcele unui lanț elementar V de la intrare la ieșire, vom nota cu V+ mulțimea arcelor care au aceiași orientare cu sensul de parcurgere de la intrare la ieșire și cu V- mulțimea arcelor orientate în sens invers.

Calculăm ε1= și ε2=

ε1 dacă V-=

și ε =

min(ε1,ε2 ) dacă V+=

Dacă ε >0 atunci fluxul g poate fi mărit .Mărim fluxul cu ε pe arcele din V+ și le micșorăm cu ε pe cele din V-

Pentru înțelegerea algoritmului trebuie reamintită noțiunea de tăietură.

Fie AX astfel încât sA și tA (unde s este intrarea rețelei și t ieșirea). Se numește tăietură de suport A mulțimea arcelor din U care intră în mulțimea A din exteriorul lui A;

Notăm:

Algoritmul se bazează pe următoarea teoremă:

Valoarea maximă a fluxului la ieșire este egală cu capacitatea minimă a unei tăieturi.

Algoritmul lui Ford-Fulkerson.

Pas1. Se construiește un flux inițial compatibil cu capacitățile arcelor rețelei (de exemplu g(u)=0, ) (un flux compatibil este un flux care verifică condiția de conservare și condiția de mărginire a fluxului)

Pas2. Cât timp există lanțuri nesaturate de la s la t se aplică criteriul de mărire.

Pentru determinarea lanțurilor nesaturate de la s la t marcăm nodurile cu etichete în felul următor:

a)Se etichetează s cu +;

b) Dacă xk este etichetat, atunci:

– se marchează cu[+xj] orice vârf xj nemarcat cu proprietatea că (xk,xj)U și (xk,xj) nu este saturat;

– se marchează cu [-xj] orice vârf xj nemarcat cu proprietatea că (xj,xk)U și g((xj,xk))0 nu este saturat;

Dacă prin acest procedeu se etichetează t atunci g este maxim și vom considera un lanț format din vârfuri etichetate între s și t pentru care aplicăm criteriul de mărire.

Algoritmul are un număr finit de pași. Într-adevăr, deoarece atât capacitățile arcelor cât și componentele fluxului sunt naturale, la fiecare mărire a fluxului, Vg crește cu cel puțin o unitate iar fluxul este mărginit (nu poate depăși capacitatea minimă a unei tăieturi)

Exemplu: Fie rețeaua din figura de mai jos. Considerăm fluxul inițial zero. Acesta poate fi mărit, ajungând la fluxul maxim 3.Intrarea este 1 și ieșirea 4. Primul număr de pe fiecare arc reprezintă capacitatea, și al doilea este fluxul.

Iată rezultatul dat de program cu următoarele intrări:

Număr de vârfuri:4

Număr de arce :6

Se dau arcele astfel (vârf1 vârf2 capacitate)

1 2 1

1 3 3

2 3 1

3 2 1

2 4 3

3 4 1

Rezultat:

Lanțurile pe care se mărește fluxul sunt:

I=(1 2 3 4 ) mărind fluxul cu 1

I=(1 3 2 4 ) mărind fluxul cu 1

I=(1 3 2 4) mărind fluxul cu 1

Tăietura minimă este formată din arcele: (1,2), (3,2), (3,4)

Fluxul maxim este 3.

program ford_fulkerson;

const nmax=20;

inf=maxint;

type info=record

c,g:integer;

end;

var a:array[1..nmax,1..nmax] of info;

n,i,p:1..nmax;

m:array[1..nmax] of integer;

gata:boolean;v:word;

procedure init;

var m,i,j,z:word;x,y:1..nmax;

begin

writeln('Dati nr de varfuri :');readln(n);

for i:=1 to n do

for j:=1 to n do

begin

a[i,j].c:=-1;

a[i,j].g:=0;

end;

writeln('Dati nr de arce:');readln(m);

for i:=1 to m do

begin

writeln('Dati arcul ',i,' si capacitatea lui: ');

readln(x,y,z);

a[x,y].c:=z;

end;

end;

procedure etichetare(k:word);

var j:word;

begin

if not gata then

for j:=1 to n do

if(a[k,j].c>=0)and (m[j]=0) and (a[k,j].c<>a[k,j].g) then

begin

m[j]:=k;

If j=n then gata:=true

else etichetare(j);

end

else

if (a[j,k].c>=0) and (m[j]=0) and (a[j,k].g<>0) then

begin

m[j]:=-k;

etichetare(j);

end;

end;

procedure marire ;

var x,y,i,l,min1,min2,min,t:word;

d:array[1..nmax] of 1..nmax;

procedure genlant(k:word);

var aux:integer;

begin

aux:=m[k];

if aux<>n+1 then

begin

if aux>0 then

begin

if min1>a[aux,k].c-a[aux,k].g then

min1:=a[aux,k].c-a[aux,k].g

end

else if min2>a[k,-aux].g then min2:=a[k,-aux].g;

genlant(abs(aux));

l:=l+1;

d[l]:=k;

end

else

begin

d[1]:=1;

l:=1;

end;

end;

begin

min1:=inf;min2:=inf;

genlant(n);

if min1<min2 then min:=min1

else min:=min2;

for i:=1 to l-1 do

begin

x:=d[i];y:=d[i+1];

if m[y]>0 then a[x,y].g:=a[x,y].g+min

else a[y,x].g:=a[y,x].g-min

end;

v:=v+min;

writeln;

write('I=(');

for t:=1 to l do

write(' ',d[t]);

write(' )');

write(' marind fluxul cu ',min,';');

end;

begin

init;

v:=0;

writeln('Lanturile pe care se mareste fluxul sunt :');

repeat

for i:=1 to n do m[i]:=0;

m[1]:=n+1;

gata:=false;

etichetare(1);

if m[n]<>0 then marire;

until m[n]=0;

writeln;

write('Taietura minima este formata din arcele: ');

for i:=1 to n do

for p:= 1 to n do

begin

If (m[p]=0) and (m[i]<>0) and (a[i,p].c>=0) then write( '(',i,',',p,') ');

end;

writeln;

writeln('Fluxul maxim este:',v);

readln;

end.

2. Problema de flux minim

Fie G=(X,U) o rețea. Pentru fiecare arc avem atașate capacitate c și fluxul g. Problema fluxului minim constă în determinarea unui flux g astfel încât fluxul la ieșire (suma fluxurilor pe arcele ce intră în ieșire) Vg să fie minim.

Vom considera c,g:UN. Pentru această problemă : g(u)c(u) pentru orice arc u U. Vom considera fluxul inițial pe fiecare arc egal cu capacitatea maximă a tuturor arcelor + 1.

Procesul de micșorare constă în :

Fie V un drum nesaturat.

Calculăm ε=

Dacă ε >0 atunci fluxul g poate fi micșorat .

Micșorăm fluxul pe fiecare arc cu ε și îl vom mări cu ε pe arcele .

Valoarea minimă a fluxului la ieșire este egală cu capacitatea maximă a unei tăieturi.

Algoritmul lui Ford-Fulkerson.

Pas1. Se construiește un flux inițial compatibil cu capacitățile arcelor rețelei (de exemplu g(u)= +1, ) (un flux compatibil este un flux care verifică condiția de conservare și condiția de mărginire a fluxului)

Pas2. Cât timp există lanțuri nesaturate de la s la t se aplică criteriul de micșorare.

Pentru determinarea lanțurilor nesaturate de la s la t marcăm nodurile cu etichete în felul următor:

a) Se etichetează s cu -;

b) Dacă xk este etichetat, atunci:

– se marchează cu [-xj] orice vârf xj nemarcat cu proprietatea că (xk,xj)U și (xk,xj) nu este saturat;

– se marchează cu [+xj] orice vârf xj nemarcat cu proprietatea că (xj,xk)U

Dacă prin acest procedeu se etichetează t atunci g este minim și vom considera un lanț format din vârfuri etichetate între s și t pentru care aplicăm criteriul de micșorare.

Exemplu: Fie rețeaua din figura de mai jos. Considerăm fluxul inițial maximul capacităților + 1 adică 9. Acesta poate fi micșorat, ajungând la fluxul minim 13. Intrarea este 1 și ieșirea 6. Primul număr de pe fiecare arc reprezintă fluxul, și al doilea, cel din paranteză, este capacitatea.

Programul are intrările:

Număr de vârfuri:6

Număr de arce:10

Se dau arcele astfel (vârf1 vârf2 capacitate)

1 2 4

1 3 6

2 3 5

3 2 3

3 5 6

2 4 7

4 5 4

5 4 3

4 6 5

5 6 8

Rezultat:

Lațurile pe care se micșorează fluxul sunt:

I=(1 2 3 5 4 6) micșorând fluxul cu 3

I=(1 2 4 5 6) micșorând fluxul cu 1

I=(1 2 4 6) micșorând fluxul cu 1

Tăietura maximă este formată din arcele: (2,4) (3,5)

Fluxul minim este:13

program flux_minim;

const nmax=20;

inf=maxint;

type info=record

c,g:integer;

end;

var a:array[1..nmax,1..nmax] of info;

n,i,p:1..nmax;

m:array[1..nmax] of integer;

gata:boolean;v:word;max:integer;

procedure init;

var m,i,j,z:word;x,y:1..nmax;

begin

writeln('Dati nr de varfuri :');readln(n);

for i:=1 to n do

for j:=1 to n do

begin

a[i,j].c:=-1;

end;

writeln('Dati nr de arce:');

readln(m);

max:=-1;

for i:=1 to m do

begin

writeln('Dati arcul ',i,' si capacitatea lui: ');

readln(x,y,z);

if max<z then max:=z;

a[x,y].c:=z;

end;

for i:=1 to n do

for j:=1 to n do

begin

a[i,j].g:=max+1;

end;

end;

procedure etichetare(k:word);

var j:word;

begin

if not gata then

for j:=1 to n do

if(a[k,j].c>=0)and (m[j]=0) and (a[k,j].c<>a[k,j].g) then

begin

m[j]:=-k;

if j=n then gata:=true

else etichetare(j);

end

else

if (a[j,k].c>=0) and (m[j]=0) then

begin

m[j]:=k;

etichetare(j);

end;

end;

procedure micsorare ;

var x,y,i,l,min,t:word;

d:array[1..nmax] of 1..nmax;

procedure genlant(k:word);

var aux:integer;

begin

aux:=m[k];

if aux<>-(n+1) then

begin

if aux<0 then

begin

If min>a[-aux,k].g-a[-aux,k].c then

min:=a[-aux,k].g-a[-aux,k].c

end;

genlant(abs(aux));

l:=l+1;

d[l]:=k;

end

else

begin

d[1]:=1;

l:=1;

end;

end;

begin

min:=inf;

genlant(n);

for i:=1 to l-1 do

begin

x:=d[i];y:=d[i+1];

if m[y]<0 then a[x,y].g:=a[x,y].g-min

else a[y,x].g:=a[y,x].g+min

end;

writeln;

write('I=(');

for t:=1 to l do

write(' ',d[t]);

write(' )');

write(' micsorand fluxul cu ',min,';');

end;

{program principal}

begin

init;

v:=0;

writeln('Lanturile pe care se micsoreaza fluxul sunt :');

repeat

for i:=1 to n do m[i]:=0;

m[1]:=-(n+1);

gata:=false;

etichetare(1);

if m[n]<>0 then micsorare;

until m[n]=0;

writeln;

write('Taietura maxima este formata din arcele: ');

for i:=1 to n do

for p:= 1 to n do

begin

if (m[p]=0) and (m[i]<>0) and (a[i,p].c>=0) then

begin

write( '(',i,',',p,') ');

v:=v+a[i,p].c;

end;

end;

writeln; writeln('Fluxul minim este:',v); readln;

end.

Bibliografie

Nicos Christofides, Graph Theory. An algorithmic approach, Academic Press, 1975.

Ioan Tomescu, Combinatorică și teoria grafurilor, Tipografia Universității București, 1978.

L. R. Ford, Jr., D. R. Fulkerson, Flows în networks, Princeton University Press, 1962.

Shimon Even, Graph algorithms, Computer Science Press, 1979.

R. Gould, Graph Theory, Emory University, 1988.

Cornelia Ivașc, Mona Prună, Bazele informaticii, Editura Petrion, București, 1995.

R. D. Busacker, T. L. Staaty, Finit graphs and networks, McGrawhill, 1968.

Claude Berge, Graphs, North-Holland, Amsterdam, 2nd rev. ed., 1985.