Detail předmětu
Grafové algoritmy
FSI-9GRAAk. rok: 2024/2025
Předmět se zaměřuje na teorii grafů a seznamuje studenty s jejími základními pojmy a algoritmy. Zabývá se následujícími tématy: Reprezentace grafu v počítači. Časová složitost algoritmů. Datové struktury pro grafové algoritmy (binární halda, disjunktní množiny, ...).
Eulerovské tahy, hamiltonovské cesty. Prohledávání grafů (do šířky, do hloubky), backtracking, metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty.
Síťové grafy. Stromy a kostry. Steinerovy stromy. Základy počítačové geometrie - grafy viditelnosti, Voroného diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.
Jazyk výuky
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Pravidla hodnocení a ukončení předmětu
Učební cíle
Studenti získají základní znalosti z teorie grafů a grafových algoritmů. Budou tak schopni modelovat pomocí grafů různé problémy z praxe a ty pak řešit pomocí grafových algoritmů.
Základní literatura
Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998. (EN)
Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004. (EN)
Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993. (EN)
Doporučená literatura
Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991. (EN)
Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002. (EN)
Elearning
Zařazení předmětu ve studijních plánech
Typ (způsob) výuky
Přednáška
Vyučující / Lektor
Osnova
2. Reprezentace grafu v počítači.
3. Časová a paměťová složitost algoritmů.
4. Prohledávání grafů, backtracking, metoda větví a mezí.
5. Aplikace úloh o cestách, nejkratší cesty, síťové grafy.
6. Eulerovské tahy, hamiltonovské cesty a kružnice.
7. Komponenty souvislosti, stromy a kostry.
8. Steinerovy stromy.
9. Voronoiovy diagramy, Delaunayho triangulace.
10. Barvení grafů, kliky.
11.-12. Toky v sítích.
13. Párování grafech.
Elearning