Grafové algoritmy (FSI-9GRA)

Akademický rok 2026/2027
Garant: doc. Ing. Jakub Kůdela, Ph.D.  
Garantující pracoviště: ÚAI všechny předměty garantované tímto pracovištěm
Jazyk výuky: čeština či angličtina
Cíle předmětu:

Cílem předmětu je seznámit studenty s teorií grafů a jejími algoritmy, které rozšiřují znalosti získané v předmětech se zaměřením na umělou inteligenci, operační výzkum, projektové řízení a počítačové sítě, a mají aplikace v technických i jiných oblastech.
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 pomocí grafových algoritmů řešit .
Výstupy studia a kompetence:
 
Prerekvizity:
 
Obsah předmětu (anotace):
 
Metody vyučování:
 
Způsob a kritéria hodnocení:
 
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
 
Typ (způsob) výuky:
    Přednáška  10 × 2 hod. nepovinná                  
Osnova:
    Přednáška 1. Definice grafu a základní pojmy.
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.
Literatura - základní:
1. Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
2. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001.
3. Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004.
4. Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998.
Literatura - doporučená:
5. Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
6. Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.
7. Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
D-APM-P prezenční studium --- bez specializace -- drzk 0 Povinně volitelný 3 1 L