Teoria grafów i sieci
Informacje ogólne
Typ:specjalnościowyKierunek:Informatyka studia licencjackie
Specjalność:Algorytmy i struktury danych
Semestr:5
Wymiar zajęć:30 godz wykładu, 15 godz ćwicz, 15 godz laboratorium
Punkty ECTS:6
Program
- Definicje podstawowe
- Drogi i cykle
- Algorytmy dla ścieżek
- Grafy eulerowskie
- Grafy hamiltonowskie
- Drzewa
- Minimalne drzewa spinające
- Spójność grafów
- Planarność grafów
- Kolorowanie wierzchołków grafów
- Kolorowanie krawędzi grafów
- Skojarzenia
- Przepływy w sieciach
- Grafowe problemy ramseyowskie
Sposób zaliczenia
egzamin pisemny z tresci poruszanych na wykładzie i ćwiczeniachLiteratura
- R.J. Wilson: Wprowadzenie do teorii grafów, PWN 1998
- R. Diesel: Graph Theory, Springer 2000
- M. Kubale i in.: Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT 2003.
