Clasele 11-12 lecția 23 - 18 mar 2015

From Algopedia
Jump to: navigation, search

Fluxuri în grafuri: metoda push-relabel

Și această lecție urmează capitolul corespunzător din Introduction to Algorithms de Cormen, Leiserson, Rivest, Stein.

Metoda push-relabel este o abordare diferită de metodele bazate pe drum de creștere, deși păstrează unele concepte, cum ar fi rețeaua reziduală. O implementare naivă obține complexitatea O(mn^{2}), iar algoritmul relabel-to-front atinge O(n^{3}).

Vizualizare

  • fiecare nod capătă un rezervor infinit
  • fiecare nod stă pe o platformă a cărei înălțime crește în timp
  • fluxul poate fi împins doar pe muchii descrescătoare
  • odată împins, fluxul continuă să existe pe muchii care ajung să urce (datorită înălțării terminației)

Definiții

Prefluxul este o relaxare a fluxului, care permite fluxului să se adune în exces în unele noduri. Prefluxul respectă capacitățile muchiilor și proprietatea de antisimetrie, dar înlocuiește condiția conservării

\sum _{{v\in V}}f(u,v)=0

cu condiția

f(V,u)\geq 0

Cantitatea e(u)\triangleq f(V,u) se numește exces. Dacă un vârf u\in V-\{s,t\} are e(u) > 0, spunem că u are exces (engl. overflows). Repetăm că această denumire nu se aplică vârfurilor s și t (de fapt, s nu va avea niciodată exces).

Funcția înălțime h:V\to {\mathbf  {N}} asociază fiecărui nod o înălțime naturală astfel încât

  1. h(s)=|V|
  2. h(t)=0 (înălțimile sursei și destinației nu se modifică niciodată)
  3. h(u)\leq h(v)+1 pentru orice muchie reziduală

Pentru clarificare, condiția (3) este o condiție pe care ne-o autoimpunem. Pe măsură ce graful rezidual și înălțimile nodurilor se modifică, condiția (3) impune limitări asupra modificărilor. De acolo va decurge complexitatea bună a metodei.

Operații de bază. Descrierea algoritmului

Operația push împinge cât de mult flux se poate de la u la v în următoarele condiții:

  1. e(u)>0 (vârful u are exces)
  2. c_{f}(u,v)>0 (muchia (u, v) are capacitate reziduală)
  3. h(u)=h(v)+1 (diferența pe verticală este de exact 1)

Operațiile push se împart în saturante și nesaturante, după cum ele saturează sau nu muchia (u, v).

  push(u, v) {
    vol = min(e[u], cf[u][v]);
    f[u][v] += vol;
    f[v][u] -=vol
    e[u] -= vol;
    e[v] += vol;
  }

Operația relabel crește înălțimea unui nod u dacă el are exces, dar toate muchiile care mai admit capacitate duc către noduri cu înălțimea mai mare sau egală cu a lui u. Operația se aplică, deci, în condițiile:

  1. e(u)>0 (vârful u are exces)
  2. \forall v\in V\,{\mbox{astfel încât}}\,c_{f}(u,v)>0,h(u)\leq h(v) (toate muchiile care ies din u merg în sus)
  relabel(u) {
    h[u] = 1 + min { h[v] | f[u][v] < c[u][v] };
  }

Inițializarea algoritmului creează un preflux saturând toate muchiile care pleacă din s.

  initPreflow(u) {
    for (u in V) {
      h[u] = e[u] = 0;
    }
    for (e = (u, v) in E) {
      f[u][v] = f[v][u] = 0;
    }
    h[s] = n;
    for (u in vecini(s)) {
      vol = c[s][u];
      f[s][u] = vol;
      f[u][s] = -vol;
      e[u] = vol;
      e[s] -= vol;
    }
  }

Algoritmul generic push-relabel nu face decât să aplice operații de push sau relabel cât timp o astfel de operație există.

  pushRelabel(u) {
    while (există o operație push sau relabel aplicabilă) {
      aplică operația push sau relabel;
    }
  }

Demonstrații

Nu este grav dacă nu memorați demonstrațiile, dar familiarizați-vă cel puțin cu enunțurile de mai jos. Ele vă vor da o înțelegere mai bună a principiilor metodei push-relabel.

Toate lemele folosesc notațiile:

  • G = (V, E) este o rețea de flux cu sursa s și destinația t;
  • f este un preflux în G;
  • G_{f}=(V,E_{f}) este rețeaua reziduală indusă de f;
  • h este o funcție înălțime în V;
  • u și v sunt vârfuri în G.

Lema 1. Dacă h(u)>h(v)+1, atunci (u,v)\notin E_{f}.

Demonstrație: Evidentă din definiția funcției-înălțime.

Lema 2. După o operație push nesaturantă pe muchia (u, v), nodul u nu mai are exces.

Demonstrație: Evidentă din implementarea operației push. Deoarece operația este nesaturantă, înseamnă că volumul ales este limitat nu de capacitatea reziduală a muchiei, ci de excesul nodului u.

Lema 3. Operația relabel este bine definită.

Demonstrație: Trebuie să arătăm că mulțimea înălțimilor din care extragem minimul este nenulă. Într-adevăr, deoarece e(u) > 0, trebuie să existe cel puțin o muchie (v, u) pentru care f(v, u) > 0. Pe inversul acelei muchii avem:

c_{f}(u,v)=c(u,v)-f(u,v)=c(u,v)+f(v,u)>0

Lema 4. Dacă u are exces, atunci i se aplică o operație push sau relabel.

Demonstrație: Dacă u are exces, atunci conform Lemei 3 există muchii reziduale care pornesc din u. Așadar, primele două condiții pentru operația push sunt întrunite. Dacă lui u nu i se poate aplica operația push, atunci cea de-a treia condiție nu este întrunită, respectiv pentru orice muchie reziduală (u, v) avem h(u) < h(v) + 1. (Nu putem avea h(u) > h(v) + 1 deoarece h nu ar fi funcție înălțime). Așadar h(u) ≤ h(v), deci ambele condiții pentru operația relabel sunt întrunite.

Lema 5. Înălțimile vârfurilor nu descresc niciodată. Când unui vârf u i se aplică operația relabel, h(u) crește cu cel puțin 1.

Demonstrație: Este evident că operația push nu afectează înălțimile. În operația relabel, extragem minimul dintr-o mulțime de noduri v pentru care h(v) ≥ h(u) și îi adăugăm 1, deci înălțimea lui u crește.

Lema 6. Pe parcursul algoritmului generic push-relabel, funcția h își păstrează proprietățile de funcție înălțime.

Demonstrație: Prin inducție. După inițializare, h(s) = n, h(t) = 0, deci primele două condiții sunt satisfăcute. Pentru condiția (3), să observăm că singura înălțime mai mare ca 0 este a lui s, deci singurele muchii pentru care h(u) > h(v) + 1 sunt muchiile (s, v), care sunt saturate. Cu alte cuvinte, condiția (3) se aplică unei mulțimi vide de muchii și este adevărată în mod trivial.

Pe parcursul algoritmului, vârfurile s și t nu suferă operații (reamintim că ele nu se încadrează ca vârfuri cu exces). Așadar, primele două condiții rămân îndeplinite.

Să considerăm acum operația relabel. Întrucât ea alege minimul înălțimilor muchiilor reziduale care pornesc din u, rezultă că h(u) ≤ h(v) după reetichetare pentru orice muchie reziduală. La intrare, dacă o muchie reziduală (w, u) întrunește condiția h(w) ≤ h(u) + 1, cu atât mai mult o va întruni și după relabel, căci h(u) crește cu cel puțin 1.

Să considerăm și operația push pe muchia (u, v). Știm că h(u) = h(v) + 1. Dacă operația este saturantă, muchia (u, v) dispare din graful rezidual, ceea ce nu adaugă, ci elimină o restricție. Operația poate și să adauge muchia (v, u) în graful rezidual, dacă nu exista deja. În acest caz, h(v) = h(u) - 1 < h(u) + 1, deci condiția (3) este îndeplinită.

Lema 7. Nu există nicio cale de la s la t în G_{f}.

Demonstrație: Dacă ar exista o cale p, am putea să o reducem fără a pierde din generalitate la o cale simplă cu cel mult n noduri și n - 1 muchii. Dar funcția h descrește cu exact o unitate pe fiecare muchie, pe când diferența între h(s) = n și h(t) = 0 este de exact n unități.

Lema 8. Dacă algoritmul generic push-relabel se termină, atunci prefluxul f pe care îl calculează este un flux maxim.

Demonstrație: Demonstrăm prin inducție că, după fiecare operație push sau relabel, f este un preflux.

  • La inițializare, f este un preflux
  • Operațiile relabel nu modifică fluxul, doar înălțimile
  • La operațiile push nu pompăm mai mult decât excesul nodului, deci excesul nu va deveni niciodată negativ.

Presupunând că algoritmul se termină, el se termină pentru că nu mai găsește operații push sau relabel de executat. Din reciproca lemei 4 deducem că orice vârf u\in V-\{s,t\} nu mai are exces. Atunci f este un flux. Mai mult, deoarece h este funcție înălțime, Lema 7 ne arată că nu există nicio cale de la s la t în G_{f}. Cu alte cuvinte, nu există drumuri de creștere, deci f este un flux maxim.

Lema 9. Dacă u are exces, atunci există o cale de la u la s în G_{f}.

Intuiție: Algoritmul începe prin a satura toate muchiile (s, u). Pentru a progresa, el va ridica înălțimea vecinilor lui s, apoi va pompa fluxul din acei vecini mai departe, propagând astfel o „frontieră” de noduri cu exces. Pentru fiecare muchie (u, v) pe care pompează flux, algoritmul va adăuga muchia reziduală (v, u). Intuitiv, se vede deci că nodurile cu exces sunt unite prin muchii reziduale de nodul sursă s.

Demonstrație: Fie u un nod cu e(u) > 0. Să presupunem că nu există o cale în G_{f} de la s la u. Atunci fie U mulțimea nodurilor către care există o cale din u și {\bar  U}=V-U. Să considerăm o muchie (x, y) cu x\in U și y\in {\bar  U}. Atunci f(x, y) ≥ 0, căci dacă f(x, y) < 0, atunci ar exista o muchie reziduală (x, y) și deci y ar trebui să aparțină lui U.

Cum muchia (x, y) a fost aleasă arbitrar, prin însumare obținem f(U,{\bar  U})\geq 0 și

e(U)\triangleq f(V,U)=f({\bar  U},U)+f(U,U)=f({\bar  U},U)=-f(U,{\bar  U})\leq 0

Dar e(U) este o sumă de numere ne-negative, deci singura soluție este ca toate să fie egale cu 0. În particular, e(u) = 0, ceea ce contrazice presupunerea inițială.

Lema 10. Funcția înălțime nu va depăși valoarea 2n - 1.

Demonstrație: Prin definiție, h(s) = n. Conform Lemei 9, din orice nod u există un drum către s mergând pe muchii reziduale. Fără a restrânge generalitatea, putem considera că drumul este simplu, deci conține cel mult n - 1 muchii. Pe fiecare din aceste muchii, (v, w), avem h[v] ≤ h[w] + 1. Însumând aceste relații pe drumul simplu, obținem h[u] ≤ h[s] + n - 1 = 2n - 1.

Calculul de complexitate

Rămâne să demonstrăm că algoritmul generic se termină. Vom face aceasta punând o limită pe cele trei tipuri de operații posibile: relabel, push saturante, push nesaturante.

Există O(n^{2}) operații relabel

Afirmația rezultă deoarece:

  • înălțimile nodurilor pornesc de la 0 și ajung la cel mult 2n - 1 (Lema 10);
  • există n - 2 noduri care pot suferi operații relabel (căci s și t prin definiție nu au exces);
  • la fiecare operație relabel înălțimea crește cu cel puțin 1 (Lema 5).

Există O(mn) operații push saturante

Să considerăm numărul de operații push saturante pe muchia (u, v), în ambele sensuri. Dacă la un moment dat pompăm flux de la u la v, atunci prin definiție h(u) = h(v) + 1. Pentru a mai putea pompa flux de la u la v, trebuie mai întâi să pompăm flux invers, de la v la u. Aceasta se poate întâmpla doar după ce nodul v se înalță cu cel puțin două unități. Printr-un argument similar, cele două noduri trebuie să se înalțe alternativ cu câte două unități, deci numărul maxim de operații push saturante pe (u, v) este 2n. Există m muchii, deci numărul total de operații push saturante în rețea este 2mn.

Există O(mn^{2}) operații push nesaturante

Demonstrația se face cu analiză amortizată, metoda potențialului. Reamintim că, la modul general, această metodă asignează o funcție potențial structurii în ansamblu. Această funcție crește puțin pentru operații ieftine și scade mult pentru operații scumpe.

Definim Φ ca fiind suma înălțimilor nodurilor cu exces:

\Phi =\sum _{{e(v)>0}}h(v)

O operație relabel va crește potențialul cu cel mult 2n - 1. Într-adevăr, operația relabel nu afectează mulțimea de noduri din Φ, iar h(u) crește cel mult de la 0 la 2n - 1.

O operație push saturantă va crește potențialul cu cel mult 2n - 1. Într-adevăr, operația push saturantă pe muchia (u, v) nu modifică înălțimile, dar poate să-l adauge pe v la mulțime, iar h(v) ≤ 2n - 1.

Contribuția totală a operațiilor relabel și push saturante la Φ este așadar 4n^{2}(m+n)

O operație push nesaturantă va scădea potențialul cu cel puțin 1. De ce? Conform Lemei 2, după o operație nesaturantă pe muchia (u, v), u nu mai are exces, deci dispare din Φ. Este posibil ca v să fi fost deja în Φ, caz în care potențialul scade cu h(u) (iar h(u) ≥ 1 ca să fi putut pompa flux „la vale”). Este posibil și ca v să intre în Φ în urma acestei operații, caz în care Φ scade cu h(u) - h(v) = 1.

Implementare

Ca să obținem și în practică algoritmul generic în O(mn^{2}), trebuie să implementăm următoarele operații:

  • relabel: cel mult O(m) (în practică vom găsi o soluție cu O(n));
  • push: O(1);
  • alegerea următoarei operații în bucla principală: O(1).

Algoritmul Relabel-To-Front

  • conceptul de muchie admisibilă
  • funcția discharge()
  • (eventual) demonstrație de complexitate
  • gap heuristic

Temă