Detail předmětu
Grafové algoritmy (v angličtině)
FIT-GALeAk. rok: 2019/2020
Předmět diskutuje různé reprezentace grafů v počítači a grafové algoritmy pro problémy typu prohledávání grafů (do hloubky, do šířky), topologické uspořádání grafů, hledání komponent grafu a silně souvislých komponent, stromy a minimální kostry, nejkratší cesty z jednoho vrcholu do všech ostatních či ze všech vrcholů do všech ostatních, maximální tok a minimální řez, maximální párování v bipartitních grafech, Eulerovské grafy a barvení grafů. U všech algoritmů je kladen důraz na pochopení principu jejich fungování a na studium složitosti navržených algoritmů.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Prerekvizity
Způsob a kritéria hodnocení
Učební cíle
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Doporučená literatura
Copy of lectures.
J. Demel, Grafy a jejich aplikace, Academia, 2002. (More about the book (http://kix.fsv.cvut.cz/~demel/grafy/))
J. Demel, Grafy, SNTL Praha, 1988. (CS)
J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize) (CS)
J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008. (EN)
J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990. (EN)
J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005. (EN)
J.L. Gross, J. Yellen: Handbook of Graph Theory (Discrete Mathematics and Its Applications), CRC Press, 2003. (EN)
R. Diestel, Graph Theory, Third Edition (http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/), Springer-Verlag, Heidelberg, 2000. (EN)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (http://www.introductiontoalgorithms.com), McGraw-Hill, 2002. (EN)
Zařazení předmětu ve studijních plánech
Typ (způsob) výuky
Přednáška
Vyučující / Lektor
Osnova
- Ú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, Kruskalův algoritmus a Primův algoritmus.
- Nejkratší cesty z jednoho vrcholu do všech ostatních vrcholů, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
- Dijkstrův algoritmus. Nejkratší cesty ze všech do 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í.
- Barvení grafů.
- Eulerovské grafy a tahy, Hamiltonovské grafy a kružnice.
Projekt
Vyučující / Lektor
Osnova
- Řešení vybraných grafových problémů a prezentace řešení (princip, složitost, implementace, optimalizace).