Clasele 11-12 lecția 21 - 4 mar 2015

From Algopedia
Revision as of 14:23, 3 March 2015 by Cata (talk | contribs) (→‎Generalizări)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Fluxuri în grafuri

(Și) pentru această lecție urmărim planul din Cormen.

Definiție

O rețea de flux este un graf G = (V, E) în care fiecare muchie are o capacitate ne-negativă. Pentru generalitate, funcția de capacitate este definită între toate perechile de noduri, deci

Dacă între două noduri u și v nu există muchie, atunci c(u, v) = 0.

Două noduri sunt de interes special în acest graf și le numim s (sursă) și t (terminație). Un flux într-o astfel de rețea este o funcție

cu proprietățile:

  1. Respectarea capacităților:
  2. Antisimetrie:
  3. Conservarea fluxului:

Valoarea fluxului se notează cu |f| și are valoarea:

Cu aceste definiții, problema fluxului maxim ne cere, dată fiind o rețea de flux, să aflăm un flux de valoare maximă în acea rețea.

Exemple din viața reală

Pentru fiecare din aceste exemple, să ne gândim ce înseamnă capacitatea, fluxul, și ce utilitate practică are găsirea unui flux maxim.

  • Rețea de conducte
  • Rețea de străzi
  • Rețea de curent electric (de altfel, conservarea fluxului este o reformulare a legii I a lui Kirchhoff).
  • Rețea de calculatoare

Ne vom folosi pentru exemplificare de modelul rețelei de conducte cu apă.

Vom vedea în curând de ce teoria permite și fluxuri negative. Din exemplele de mai sus ar putea părea că nu avem nevoie de ele în practică. Remarcăm, totuși, că dacă și , atunci . De ce? Deoarece este singurul mod în care următoarele trei condiții pot fi îndeplinite:

  1. (respectarea capacității pe muchia (u, v))
  2. (respectarea capacității pe muchia (v, u))
  3. (antisimetria fluxului)

Așadar, fluxul nu poate apărea pe muchii inexistente.

Rețele reziduale

Ce este un drum de creștere? Intuitiv, deschidem un robinet în s și ne întrebăm ce debit poate suporta rețeaua de flux spre t. Începem prin a găsi o cale de la s la t astfel încât toate conductele (muchiile) să fie nesaturate. Această cale se numește drum de creștere. Pe această cale mai putem pompa apă, în debit egal cu minimul debitului disponibil pe oricare dintre conducte. Apoi repetăm, ținând cont că acum capacitățile unor muchii sunt efectiv diminuate de fluxul deja existent.

Să formalizăm această noțiune intuitivă.

Fie un graf G = (V, E) și un flux f în acest graf (nu neapărat maxim). Definim capacitatea reziduală a unei muchii ca

Așadar, este fluxul care mai poate fi pompat prin muchie. Observăm un comportament straniu aici. Dacă și , atunci , dar și ! Cu alte cuvinte, avem opțiunea, mai târziu, să pompăm înapoi o parte din apă (reducând debitul pe muchia (u, v)), dacă prin aceasta obținem un drum de creștere.

// Exemplu grafic

Un flux f induce o rețea de flux reziduală în graf, definită ca , unde mulțimea de muchii este

Așadar, rețeaua reziduală constă din muchiile prin care mai putem pompa flux, fie în sensul normal, fie în sensul invers. Rețeaua reziduală este întotdeauna formată din muchii din E și/sau inversele lor. Acest lucru este util deoarece numărul de muchii din Ef este tot O(m).

Drumuri de creștere

Fie G = (V, E) o rețea de flux; fie f un flux în această rețea și fie Gf rețeaua reziduală. Un drum de creștere este o cale p de la s la t în Gf. Capacitatea reziduală a acestei căi este minimul capacităților reziduale pe oricare din muchiile căii.

Intuitiv, drumul de creștere este o cale pe care încă mai putem pompa apă fără a satura nicio conductă. Ce este mai interesant este că drumul de creștere poate fi modelat ca un flux. Să găsim împreună funcția care ar modela acest flux.

Fluxuri în grafuri reziduale

Următoarea lemă este cheia algoritmilor de flux maxim bazați pe drumuri de creștere.

Lemă: Fie G = (V, E) o rețea de flux; fie f un flux în această rețea; fie Gf rețeaua reziduală și fie f′ un flux în Gf. Atunci f + f′ este un flux în G cu valoarea

Demonstrație: Vom demonstra întâi că f + f′ este un flux (așadar că respectă cele trei proprietăți ale unei funcții de flux), apoi că are valoarea .

Metoda Ford-Fulkerson

Metoda Ford-Fulkerson este o metodă generală pentru găsirea unui flux maxim.

Notă: O metodă nu specifică algoritmul exact, ci doar principiul. Similar, metoda „adaugă cea mai ușoară muchie care traversează o tăietură” este o metodă de aflare a APM. Din ea decurg algoritmii lui Kruskal și Prim.

Metoda Ford-Fulkerson se bazează pe drumuri de creștere. Ea caută drumuri de creștere și recalculează rețeaua reziduală. Când nu mai găsește drumuri de creștere, fluxul obținut este maxim:

  f = 0;
  cât timp există un drum de creștere ''p''
    f += f_p

Am vrea să demonstrăm că, într-un graf G, un flux f este maxim dacă și numai dacă în rețeaua reziduală nu mai există drumuri de creștere. Demonstrația într-o direcție este banală: dacă f este maxim, atunci este destul de evident că nu mai există drumuri de creștere, căci am putea adăuga capacitatea reziduală a acelui drum la f pentru a obține un flux și mai mare.

Pentru a demonstra reciproca, mai avem de (re)introdus o noțiune: tăieturile în grafuri. Nu cunosc nicio demonstrație fără acest pas intermediar, dar nu contează -- pasul introduce noțiuni utile.

Tăieturi în grafuri

Am vorbit despre tăieturi când am învățat arborii parțiali minimi (vă amintiți)? Ele sunt partiții ale grafului în două submulțimi de noduri.

În special, într-o rețea de flux o tăietură (S, T) este o partiție a lui V cu proprietatea că și .

Pentru simplitate, extindem acum notațiile funcțiilor f și c de la simple noduri la submulțimi de noduri. Așadar,

și

Definiții:

  • Fluxul printr-o tăietură (S, T) este f(S, T).
  • Capacitatea unei tăieturi (S, T) este c(S, T).
  • Tăietura minimă a rețelei este o tăietură cu capacitate minimă între toate tăieturile posibile.

// Exemplu grafic. Este important de subliniat că f(S, T) include și muchii spre stânga, dar c(S, T) include doar muchii spre dreapta.

Lemă: Fluxul prin orice tăietură este același.

Demonstrație: cu noua noastră notație, urmărim să demonstrăm că . Într-adevăr,

Ce rezultă de aici? Că niciun flux f în G nu poate depăși capacitatea tăieturii minime în G (și, evident, nici a oricărei alte tăieturi). Teorema finală (și gata, ne oprim cu teoria), spune că există un flux care și atinge această limită superioară.

Teorema de flux maxim / tăietură minimă (Max-flow min-cut)

Teoremă: Fie un graf G = (V, E) și un flux f în G. Următoarele trei condiții sunt echivalente:

  1. f este flux maxim în G"'.
  2. Rețeaua reziduală nu mai conține drumuri de creștere.
  3. Există o tăietură (S, T) pe care f o saturează.

Demonstrație: este banal. Și se demonstrează ușor: dacă f nu ar fi maxim, atunci există un flux f′ > f. Dar acel flux ar depăși capacitatea tăieturii (S, T).

Pentru , fie S mulțimea nodurilor la care există drum din s în rețeaua reziduală. Fie T = V - S. Demonstrăm că (S, T) este tăietură și că toate muchiile sunt saturate, deci f(S, T) = c(S, T).

Algoritmul Ford-Fulkerson

Algoritmul naiv caută orice drum de creștere, de exemplu cu o parcurgere în adâncime. Problema este că complexitatea lui depinde de valoarea fluxului. Ea este pentru capacități naturale și este nedefinită pentru capacități reale.

// Exemplu grafic -- caz patologic.

Algoritmul Edmonds-Karp

Edmonds-Karp caută drumurile de creștere cu o parcurgere în lățime. Aceasta înseamnă că drumul de creștere găsit va avea lungime minimă (ca număr de muchii în rețeaua reziduală).

Lemă: Pentru orice nod , cu fiecare iterație a algoritmului, distanța minimă crește monoton.

Demonstrație: Prin reducere la absurd.

Teoremă: Algoritmul face cel mult O(VE) iterații.

Demonstrație: Orice iterație a algoritmului saturează cel puțin o muchie. Arătăm că o muchie poate fi saturată de cel mult ori. Există O(m) muchii în total. Rezultă că algoritmul nu poate depăși O(mn) iterații.

Întrucât complexitatea unei iterații (BFS) este O(m), rezultă că Edmonds-Karp are complexitatea .

Algoritmul lui Dinic

  • graf stratificat
  • faze, iterații
  • distanța de la s la t în graful stratificat crește cu 1 după fiecare fază
  • fiecare iterație elimină o muchie din graful stratificat, deci pot exista cel mult m iterații într-o fază
  • fiecare iterație are complexitate O(n), căci trebuie să caute un drum înapoi de la t la s și să mențină graful stratificat
  • rezultă o complexitate totală de
  • comparație cu implementarea de pe Infoarena

Generalizări

  • Grafuri cu surse / terminații multiple
  • Capacități în noduri

Temă