1. Ce problema rezolvam?
Avem o retea orientata cu o sursa S, o destinatie T si capacitati c(u,v) pe arce. Cautam cel mai mare flux total care poate pleca din S si ajunge in T.
Regulile unui flux
- Capacitate: 0 ≤ φ(u,v) ≤ c(u,v).
- Conservare: in fiecare nod intermediar, fluxul care intra este egal cu fluxul care iese.
- Valoarea fluxului: fluxul net iesit din S (egal cu cel intrat in T).
Notatia de pe arce
De exemplu, 1/3 inseamna ca circula 1 unitate pe un arc ce poate transporta maximum 3 unitati. Capacitatea reziduala directa este 3 - 1 = 2.
Forma standard din material: nodul initial este x1 = S, iar nodul final este xn = T. Se porneste de la fluxul nul.
2. Etapa I: incarcam drumurile S → T
Materialul propune examinarea drumurilor in ordine lexicografica. Pentru fiecare drum format din arce directe, calculam cat flux mai poate fi adaugat fara depasirea vreunei capacitati:
Adaugam ΔD pe fiecare arc al drumului. Cel putin un arc devine saturat. Repetam pana nu mai exista drum S → T format numai din arce directe cu capacitate libera.
Atentie: absenta unui asemenea drum direct nu inseamna ca fluxul este maxim. Alegerile anterioare pot fi corectate prin redistribuiri.
3. Etapa II: redistribuirea fluxului
Pentru a corecta alegerile din prima etapa, cautam un lant de ameliorare in reteaua reziduala. Acesta poate parcurge un arc fie in sensul lui, fie in sens invers.
Arc direct: marcaj [+xi]
Dintr-un nod marcat xi putem marca xj daca exista arcul xi → xj si mai avem capacitate libera:
Pe acest arc putem adauga flux.
Arc invers: marcaj [-xi]
Din xi putem ajunge inapoi in xj daca exista arcul original xj → xi si pe el circula deja flux:
Pe acest arc putem scadea fluxul existent, eliberand capacitate pentru alta ruta.
Algoritmul de marcare
- Marcam S cu 0.
- Din fiecare nod marcat extindem marcajele prin arce directe cu loc liber si prin arce inverse cu flux pozitiv.
- Daca marcam T, reconstruim lantul de la T spre S urmarind marcajele.
- Calculam ΔL: minimul capacitatilor reziduale ale tuturor pasilor lantului.
- Adaugam ΔL pe arcele directe si scadem ΔL pe cele parcurse invers. Stergem marcajele si reluam.
- Daca T nu mai poate fi marcat, fluxul este maxim.
Corectie explicita fata de PDF: la pasul 4 din etapa II, materialul afirma ca daca T este marcat, fluxul este maxim. Aceasta conditie este inversata. Daca T este marcat, exista o ameliorare; daca T nu poate fi marcat, fluxul este maxim. Simularea foloseste regula corecta.
4. Exemplu complet, pas cu pas
Reteaua initiala are 3 surse (I1, I2, I3) si 3 destinatii (D1, D2, D3). Primul pas o transforma in forma standard, prin introducerea supersursei S si a superdestinatiei T. Alege ordinea drumurilor pentru a compara fluxurile obtinute in etapa I.
Pe fiecare arc este afisat flux / capacitate. Arcele saturate sunt rosii; cele mov sunt arcele pe care fluxul este redus. S si T apar abia dupa standardizare.
Istoricul pasilor (click pentru navigare)
De unde provin capacitatile?
Capacitatile sunt date ale problemei, exprimate in unitati de marfa transportabile pe ora. Ele reprezinta limite de expediere, de receptie sau de transport ale legaturilor. Au fost alese intentionat diferite pentru a face vizibile constrangerile.
| Tip | Arce si capacitati | Interpretare |
|---|---|---|
| Surse | S-I1: 13; S-I2: 17; S-I3: 9 | Oferta maxima a celor trei surse |
| Transport | I1-A: 16; I2-B: 21; I3-C: 12; A-B: 11; A-D2: 19; B-D1: 23; C-D3: 14 | Capacitatile legaturilor fizice |
| Destinatii | D1-T: 17; D2-T: 13; D3-T: 9 | Cererea maxima acceptata |
Observatie: etapa I poate termina cu fluxuri diferite in functie de ordinea drumurilor. Etapa II trebuie sa duca in ambele cazuri la acelasi flux maxim.
5. De ce stim ca fluxul este maxim?
La ultimul pas, reteaua reziduala nu mai permite marcarea lui T din S. Nodurile marcate definesc partea V a taieturii minime, iar restul nodurilor formeaza W. In exemplul nostru, toate arcele de la supersursa sunt saturate.
Valoarea fluxului este egala cu capacitatea unei taieturi. Conform teoremei flux maxim - taietura minima, solutia este optima. Taietura apare evidentiata grafic numai la ultimul pas al simularii.
6. Intrebari pentru studenti
1. De ce nu este suficient sa incarcam numai drumurile directe?
Pentru ca o alegere anterioara poate ocupa un arc care ar fi fost mai util altui drum. Un lant rezidual cu arc invers permite anularea partiala a alegerii si redistribuirea fluxului.
2. Ce inseamna marcajul [-B] al nodului A?
Ca am ajuns la A din B folosind invers arcul original A → B, pe care exista deja flux pozitiv. Daca amelioram lantul, fluxul de pe A → B se reduce.
3. De ce Δ este minimul capacitatilor reziduale de pe lant?
Pentru ca aceeasi cantitate trebuie modificata pe tot lantul, iar pasul cu cea mai mica rezerva limiteaza cresterea posibila.
4. Cand ne oprim si ce taietura obtinem?
Cand T nu mai poate fi marcat. Nodurile marcate formeaza V, iar cele nemarcate formeaza W. Taietura (V,W) este minima.
5. Ar putea o alta ordine a drumurilor sa evite redistribuirea?
Da. Da. Selecteaza ordinea de jos in sus: obtinem direct fluxul 39. De sus in jos obtinem initial 28, apoi redistribuim si incarcam drumul eliberat. Valoarea maxima finala ramane 39.