|
Vyučující
|
-
Masopust Tomáš, doc. RNDr. Ph.D., DSc.
|
|
Obsah předmětu
|
Osnova přednášek: 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 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ů
|
|
Studijní aktivity a metody výuky
|
|
Přednášení, Demonstrace
|
|
Výstupy z učení
|
Studenti získají základní znalosti grafů a grafových algoritmů včetně analýzy jejich složitosti.
Získané dovednosti, znalosti a kompetence: Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.
|
|
Předpoklady
|
Základní znalost diskrétní matematiky a schopnost algoritmického myšlení.
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Písemná zkouška, Seminární práce
Aktivní účast v hodině. Plnění zadaných úkolů. Složení závěrečné zkoušky.
|
|
Doporučená literatura
|
-
J. Demel. (2002). Grafy a jejich aplikace. Academia.
-
J. Demel. (1988). Grafy. SNTL Praha.
-
J.A. Bondy, U.S.R. Murty. (2008). Graph Theory. Springer.
-
J.A. McHugh. (1990). Algorithmic Graph Theory. Prentice-Hall.
-
J.L. Gross, J. Yellen. (2005). Graph Theory and Its Applications. Chapman & Hall/CRC.
-
R. Diestel. (2017). Graph Theory. Springer-Verlag, Heidelberg.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest. (2002). Introduction to Algorithms. McGraw-Hill.
|