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 Jump to 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(VE²)
- 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 G_f
  - dacă algoritmul se termină, prefluxul f este flux maxim
- complexitate O(V²E)
  - 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(V³).
  - demonstrație: limitarea numărului de operații relabel / saturating push / nonsaturating push

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Note_de_curs,_clasele_11-12,_1_februarie_2013&oldid=6245"

Navigation menu