Wykład 8. Skojarzenia i przepływy (część II)

Zagadnienia, które były poruszone na wykładzie (niektóre z nich mogą zostać przeniesione do kolejnego wykładu o tej samej nazwie, jeśli taki się odbędzie):

  • Dokończenie nietrywialnych zastosowań twierdzenia o maksymalnym przepływie i minimalnym przekroju.
  • Skojarzenie: postawienie problemu, algorytm oparty na ścieżkach. powiększających z udoskonaleniem Tomka Idziaszka.
  • Pokrycie wierzchołkowe i maksymalny zbiór niezależny w grafie dwudzielnym.
  • Twierdzenie Mengera (wersja krawędziowa i wierzchołkowa).
  • Maksymalny przepływ o minimalnym koszcie (jeśli zdążymy).

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

Dostępne materiały: Nagrania.