Wykład 3. Skojarzenia i przepływy (część I)

 Zagadnienia poruszone na wykładzie:

  • Przepływ dla krawędzi jednostkowych - postawienie problemu.
  • Schemat Forda-Fulkersona.
  • Twierdzenie o maksymalnym przepływie i minimalnym przekroju.
  • Uogólnienie problemu maksymalnego przepływu dla krawędzi o dowolnych przepustowościach.
  • Algorytm Edmondsa-Karpa.
  • Zmodyfikowany algorytm Dinica.
  • Przykład zadania które pokazuje nietrywialne zastosowanie maksymalnego przepływu.

Wykład poprowadził Marek Cygan. Lokalizacja: 3150. Termin: 10.03.2008, 16:15-17:45.

Dostępne materiały: Nagrania, Notatki.