Wykład 17. Końcówka algorytmów grafowych

 Ostatnie klasyczne algorytmy grafowe, jakie pozostały do dobicia:

  • 2-SAT raz jeszcze.
  • Funkcja low, mosty, punkty artykulacji, dwuspójne składowe.
  • MST (najtańsze drzewo rozpinające), zastosowania (w tym zadanie Aviamachinations z SGU).

Wykład poprowadził Marek Cygan. Lokalizacja: 3130. Termin: 31.03.2009, 16:15-18:00.

Tutaj znajdują się notatki Bartka Nowierskiego na temat mostów, punktów artykulacji i dwuspójnych składowych (Uwaga, znajduje się tam nieprawdziwe stwierdzenie, które mówi że most łączy dwa punkty artykulacji). Załączam również kody Kuby Radoszewskiego powstałe na bazie materiałów z podanej strony: mosty i punkty artykulacji oraz dwuspójne. Jako ćwiczenie polecam rozwiązać następujące zadanie

Dostępne materiały: Nagrania.

Linki

Czy moglibyście naprawić linki do materiałów dodatkowych, które po przenosinach na was.zaa.mimuw.edu.pl stały się nieaktualne?