Note de curs, clasele 11-12, 25 ianuarie 2013

Prezentare Ceata.org

• Tibi Turbureanu de la Fundația Ceata a ținut o scurtă prezentare despre Temelia, o bibliotecă de structuri de date și algoritmi.

Fluxuri maxime

• rețea de flux -- capacitate, simetrie, conservarea fluxului
• valoarea fluxului |f| = Σ f(s, v)
• problemă: găsirea unui flux de valoare maximă
• exemple din viața reală: transporturi, curenți
• cazurile cu surse / terminații multiple se reduc la cazul cu sursă / terminație unică
• proprietăți (cu demonstrații)
  • f(X, X) = 0;
  • f(X, Y) = -f(Y, X);
  • f(X ∪ Y, Z) = f(X, Z) + f(Y, Z) și f(Z, X ∪ Y) = f(Z, X) + f(Z, Y)
• lemă: f(s, V) = f(V, t)
• suma a două fluxuri: respectă simetria și conservarea, dar încalcă (posibil) capacitatea
• Ford-Fulkerson (metodă, nu algoritm)
• rețea reziduală, c_f(u, v) = c(u, v) - f(u, v)
• lemă: Dacă f' este flux rezidual în G_f, atunci f + f' este flux în G
  • demonstrație: verificarea celor 3 proprietăți și a valorii | f + f' |
• drum de creștere p
  • exprimarea sa ca flux (c_f(p) și -c_f(p) de-a lungul căii, 0 în rest)
• lemă: |f + f_p| este flux în G (evidentă din lema precedentă)
• tăietură: (S, T), cu s ∈ S și t ∈ T. Flux (ambele sensuri), Capacitate (doar s → t).
• tăietură minimă (dpdv al capacității)
• fluxul prin orice tăietură este constant și egal cu f(S, T) = |f|
• Fluxul este limitat de capacitatea oricărei tăieturi
• Max-flow min-cut:
  1. f este flux maxim;
  2. G_f nu conține drumuri de creștere;
  3. fluxul saturează capacitatea vreunei tăieturi în G.
• algoritmul FF brut: O(E |f| ). Exemplu când chiar găsește |f| drumuri de creștere.
• algoritmul Edmonds-Karp, bazat pe BFS
  • analiza de complexitate rămâne pentru data viitoare