Głównym celem kursu jest przedstawienie klasycznych zagadnień teorii grafów i ich zastosowań do rozmaitych problemów; w tym z zakresu zarządzania i ekonomii. Podczas omawiania podstawowych własności grafów prezentować będziemy algorytmy pozwalające wyznaczać te właściwości. Opisane algorytmy będą analizowane i wykorzystane do rozwiązywania zadań praktycznych.
Program kursu:
- Podstawowe definicje teorii grafów.
- Przykłady grafów.
- Poruszanie się po grafach; problem najkrótszej drogi.
- Grafy eulerowskie i półeulerowskie; problem chińskiego listonosza.
- Drzewa i lasy; problem minimalnych połączeń, problem zliczania izomerów.
- Grafy hamiltonowski i półhamiltonowskie; problem komiwojażera.
- Grafy planarne.
- Grafy geometrycznie dualne.
- Kolorowanie grafów; problem przechowywania chemikaliów.
- Skojarzenia; problem kojarzenia małżeństw, problem harmonogramu zajęć.
- Nauczyciel: Morawiec Janusz