Problema fluxului maxim

Elemente teoretice de baza

O retea de flux este un graf orientat G=(V,E) cu 2 noduri speciale (sursa si destinatia).

Fiecarei muchii (u,v) a grafului ii este asociata o valoare cap(u,v) numita capacitatea acelei

muchii. Daca nu exista nici o muchie de la un nod u la un nod v, vom defini cap(u,v)=0.

Un flux f intr-o retea de flux G=(V,E) este o functie definita pe VxV, avand valori reale,

care respecta urmatoarele conditii:

- pentru orice u si v din V, cap(u,v)>=f(u,v) (limitare impusa de capacitati)

- pentru orice u si v din V, f(u,v)=-f(v,u) (anti-simetrie)

- pentru orice u, diferit de s si t, din V,  ( , )  0 vV

f u v (conservarea fluxului)

Aceste 3 conditii reies si in mod intuitiv:

- fluxul pe fiecare muchie nu trebuie sa depaseasca capacitatea muchiei

- fluxul de la un nod u la un nod v poate fi privit ca flux negativ, avand aceeasi valoare

absoluta, de la v la u

- cu exceptia sursei si destinatiei, cantitatea de flux care intra intr-un nod este egala cu

cantitatea de flux care iese dintr-un nod

O circulatie intr-o retea de flux este un flux pentru care proprietatea de conservare a

fluxului se aplica si nodurilor sursa si destinatie. Astfel, reteaua de flux poate fi considerata ca

neavand un nod sursa si unul destinatie. In mod intuitiv, fluxul intr-o astfel de retea poate fi privind

ca “circuland” in cicluri in interiorul retelei.

O muchie (u,v) se numeste saturata daca f(u,v)=cap(u,v). Un drum P in reteaua de flux P

este saturat de un flux f daca cel putin una din muchiile ce alcatuiesc drumul este saturata.

In figura 1. este prezentata o retea de flux cu fluxul reprezentat pe muchii. Numerele

asociate muchiilor sunt in formatul capacitate / flux.

Figura 1. O retea de flux si un flux in aceasta retea (s=sursa, t=destinatia).

Fiind data o retea de flux G=(V,E) cu sursa s si destinatia t si o functie de flux f, valoarea

fluxului este definita ca fiind  vV

f (s,v) si se noteaza |f|.

Problema fluxului maxim se defineste ca reprezentand determinarea acelei functii de flux

f pentru care |f| este maxim.

Algoritmul Ford-Fulkerson

Intrare: o retea de flux G=(V,E)

Iesire: un flux maxim f in reteaua G

1. Fie f(u,v)=0 pentru orice pereche de noduri (u,v) ale lui G

2. Construieste reteaua reziduala Gf

3. cat timp exista un flux pozitiv in reteaua reziduala Gf executa:

3.1. construieste un flux pozitiv f* in Gf

3.2. fie f = f + f* noul flux in G

3.3. construieste noua retea reziduala Gf

Algoritmul Ford-Fulkerson pentru determinarea fluxului maxim intr-o retea de flux.

Metoda saturarii celui mai scurt drum

Metoda saturarii celui mai scurt drum este o metoda de succes in construirea fluxului f* in

reteaua reziduala Gf deoarece limiteaza destul de mult numarul de iteratii ale ciclului “cat timp”.

Lungimea unui drum este calculata ca fiind numarul de muchii din care este alcatuit drumul

respectiv. In continuare vom presupune de fiecare data ca graful are N noduri si M muchii.