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

Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.

Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.

Student si v první části přednášek zopakuje důležité algoritmy na systematické prohledávání grafů včetně ukázek toho, jak se u algoritmů dokazuje korektnost. Dále se postupuje k náročnějším algoritmům na hledání nejkratších cest a dalších pokročilejších vlastností zadaného grafu. Vždy je kladen důraz na pochopení principu algoritmu a detailní diskuzi případně implementace (včetně vhodný datových struktur a jejich časově/prostorových složitostí). Kromě samotných grafových algoritmů se student zlepší ve schopnosti formálně popisovat algoritmy a odhadovat jejich složitost. V rámci projektu si vyzkouší modifikaci, implementaci a experimentování s některými vybranými pokročilejšími grafovými algoritmy.

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

• Copy of lectures.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (http://www.introductiontoalgorithms.com), McGraw-Hill, 2002.
• J. Demel, Grafy, SNTL Praha, 1988.
• J. Demel, Grafy a jejich aplikace, Academia, 2002. (More about the book (http://kix.fsv.cvut.cz/~demel/grafy/))
• R. Diestel, Graph Theory, Third Edition (http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/), Springer-Verlag, Heidelberg, 2000.
• J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
• J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008.
• J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005.
• J.L. Gross, J. Yellen: Handbook of Graph Theory (Discrete Mathematics and Its Applications), CRC Press, 2003.

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. Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly.
13. Barvení grafů.

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

Bodové hodnocení výsledků půlsemestrální zkoušky (max. 15 bodů) a vypracovaných projektů (max. 25 bodů).

Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů, závěrečná semestrální zkouška. 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.