Grafové algoritmy

• 39 hod. přednášky
• 13 hod. projekty

• 60 bodů závěrečná zkouška (písemná část)
• 15 bodů půlsemestrální test (písemná část)
• 25 bodů projekty

Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.
Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.

Základní znalost diskrétní matematiky a schopnost algoritmického myšlení.

• Text přednášek v elektronické podobě.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3. vydání, 1312 s., 2009.
• J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize)
• J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
• K. Erciyes: Guide to Graph Algorithms (Sequential, Parallel and Discributed). Springer, 2018.

• A. Mitina: Applied Combinatorics with Graph Theory. NEIU, 2019.

1. Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu.
2. Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů.
3. Topologické uspořádání vrcholů a hran, test acykličnosti grafu.
4. Komponenty grafu, silně souvislé komponenty, příklady.
5. Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus.
6. Růst minimální kostry, algoritmy Kruskala a Prima.
7. Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
8. Dijkstrův algoritmus. Nejkratší cesty ze všech vrcholů.
9. Nejkratší cesty a násobení matic, Floyd-Warshallův algoritmus.
10. Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus.
11. Párování v bipartitních grafech, maximální párování.
12. Barvení grafů, chromatický polynom.
13. Eulerovské grafy a tahy, problém čínského pošťáka, Hamiltonovské kružnice a cykly.

1. Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).

• Půlsemestrální písemná zkouška (max. 15 bodů)
• Hodnocený projekt (max. 25 bod)
• Závěrečná písemná zkouška (max. 60 bodů)
• Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.

Pokud v průběhu semestru student onemocní nebo se vyskytne jiná překážka ve studiu, je třeba tuto překážku řádně ohlásit a doložit. Pak k ní lze přihlédnout a přizpůsobit jí hodnocení:

• U projektu může student požádat příslušného učitele o přiměřené prodloužení termínu pro odevzdání.
• Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může přednášejícího požádat, aby body za půlsemestrální zkoušku byly odvozeny od bodového zisku u prvního termínu zkoušky, kterého se zúčastní.