Předmět Grafové algoritmy (FIT-GAL)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu FIT-GAL - Grafové algoritmy, Fakulta informačních technologií, Vysoké učení technické v Brně (VUT).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.
Osnova
Osnova přednášek:Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu. Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů. Topologické uspořádání vrcholů a hran, test acykličnosti grafu. Komponenty grafu, silně souvislé komponenty, příklady. Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus. Růst minimální kostry, algoritmy Kruskala a Prima. Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech. Dijkstrův algoritmus. Nejkratší cesty ze všech vrcholů. Nejkratší cesty a násobení matic, Floyd-Warshallův algoritmus. Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus. Párování v bipartitních grafech, maximální párování. Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly. Barvení grafů.Osnova ostatní - projekty, práce:Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).
Literatura
Text přednášek. 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, McGraw-Hill, 2002. J. Demel, Grafy, SNTL Praha, 1988. J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize) R. Diestel, Graph Theory, Third Edition, 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.
Požadavky
Základní znalost diskrétní matematiky a schopnost algoritmického myšlení.
Garant
prof. RNDr. Alexandr Meduna, CSc.
Vyučující
prof. RNDr. Alexandr Meduna, CSc.