Obsah:
- Připomenutí základních pojmů z teorie grafů.
- Reprezentace grafů v počítači, vhodnost reprezentací.
- Základní metody průchodů grafů, prohledávání grafů do hloubky a do šířky.
- Dostupnost v grafu, hranová a vrcholová souvislosta komponenty grafu.
- Délka cesty v grafu
- Kostry grafu
- Hledání eulerovských cest a cyklů, eulerovské grafy, hledání hamiltonovské cesty a cyklu.
- Toky v sítích
- Párování v bipartitních a obecných grafech
- Klikovost grafu, hledání nezávislé množiny vrcholů, barvení grafů
Odborná literatura:
- Moodle
- Demel J.: Grafy, SNTL, Praha, 1989
- Fronček D.: Úvod do teorie grafů, SLU Opava, 1999.
- Kučera L.: Kombinatorické algoritmy, SNTL Praha, 1991
- Večerka A.: Grafy a grafové algoritmy, PřF UP Olmouc, 2007.
|