Algorytmy grafowe i kombinatoryczne 1000-2M09AGK
1. Spójność wierzchołkowa i krawędziowa.
2. Ścieżki ważone. Minimalne drzewa rozpinające.
3. Maksymalny przepływ. Drzewo Gomory-Hu.
4. Najliczniejsze skojarzenia w grafach dwudzielnych i dowolnych. Problem stabilnych małżeństw.
5. Kolorowanie wierzchołkowe. Wielomiany chromatyczne.
6. Kolorowanie krawędziowe. Twierdzenia Vizinga i Petersena.
7. Rozpoznawanie grafów planarnych. Twierdzenie o separatorach i jego zastosowania.
8. Grafy doskonałe: grafy interwałowe, grafy cięciw, grafy permutacji.
9. Zliczanie i generowanie obiektów kombinatorycznych.
Rodzaj przedmiotu
Założenia (lista przedmiotów)
Literatura
1. W. Lipski, Kombinatoryka dla programistów, WNT.
2. A. Aho, J. Hopcroft, J. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN.
3. Reinhard Diestel, Graph Theory, Springer 2006.
4. Christos H. Papadimitriou, Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications 1998.
5. Laszlo Lovasz, Matching Theory, American Mathematical Society 2009.
6. Wybrane artykuły i rozdziały z różnych książek.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: