Note de curs, clasele 11-12, 1 februarie 2013

From Algopedia
Revision as of 14:11, 1 February 2013 by Cata (talk | contribs) (Created page with "== Scurtă recapitulare == * rețele de flux * teorema max-flow min-cut * metoda Ford-Fulkerson ** cu drum de creștere găsit prin DFS => O(|f| * E) == Algoritmi de flux maxim...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Scurtă recapitulare

  • rețele de flux
  • teorema max-flow min-cut
  • metoda Ford-Fulkerson
    • cu drum de creștere găsit prin DFS => O(|f| * E)

Algoritmi de flux maxim

  • Algoritmul Edmonds-Karp (drumul de creștere găsit cu BFS)
    • complexitate O(VE2)
    • demonstrație: distanțele de la s la orice nod u cresc cu fiecare iterație a grafului rezidual
  • Algoritmul push-relabel
    • imagine conceptuală
    • noțiuni: preflux, funcție înălțime
    • operații: push, relabel
    • demonstrații de corectitudine:
      • h rămâne funcție înălțime pe durata algoritmului
      • h crește mereu
      • nu există cale de la s la t în Gf
      • dacă algoritmul se termină, prefluxul f este flux maxim
    • complexitate O(V2E)
      • demonstrație: limitarea numărului de operații relabel / saturating push / nonsaturating push
  • Algoritmul relabel-to-front
    • noțiuni: muchii admisibile, rețea admisibilă, listă reordonabilă de noduri
    • operația de descărcare a unui nod
    • algoritmul general
    • demonstrație de corectitudine:
      • f este un flux maxim în final
      • lista de noduri este o sortare topologică a rețelei admisibile
    • complexitate: O(V3).
      • demonstrație: limitarea numărului de operații relabel / saturating push / nonsaturating push