Zagadnienia na egzamin z Algorytmów Grafowych

1. Kolorowanie grafów.
• twierdzenia Brooksa, Vizinga i Königa
• NP.-zupełność
• kolorowanie grafów planarnych
• kolorowanie sqrt(n) kolorami
• algorytm Cole’a
• kryteria 3-kolorowalności
2. Przepływy
• tw. o maksymalnym przepływie i minimalnym przekroju
• algorytmy: Forda-Fulkersona, Edmonda-Karpa, Dinica, 3-ch Hindusów, przedprzepływowe
• zastosowania
3. Planarność
• wzór Eulera i zastosowania
• tw. Kuratowskiego
• rozpoznawanie i rysowanie grafów planarnych
• separatory
4. Przeszukiwanie w głąb i zastosowania
• dwuspójne i silnie-spójne składowe
• st-numeracja
5. Grafy doskonałe
• grafy interwałowe i grafy skrótów
6. Problemy ścieżkowe
• algorytmy: Dijkstry, Forda-Bellmana, Johnsona
• cykle i ścieżki Eulera