M8160 Grafové algoritmy

Přírodovědecká fakulta
jaro 2000
Rozsah
2/1/0. 5 kr. Ukončení: zk.
Vyučující
doc. RNDr. Libor Polák, CSc. (přednášející)
Garance
doc. RNDr. Libor Polák, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Libor Polák, CSc.
Předpoklady
M5140 Kombinatorika a teorie grafů
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
  • Matematika (program PřF, M-MA, směr Diskrétní matematika)
  • Matematika (program PřF, N-MA, směr Diskrétní matematika)
Osnova
  • Elementární grafové algoritmy (reprezentace grafů, prohledávání do šířky, prohledávání do hloubky, topologické uspořádání, silně souvislé komponenty). Minimální kostry (růst minimální kostry, algoritmy Kruskala a Prima). Nejkratší cesty z jediného vrcholu (nejkratší cesty a relaxace, Dijkstrův algoritmus, Bellman- Fordův algoritmus, nejkratší cesty v orientovaných acyklických grafech). Nejkratší cesty mezi všemi dvojicemi vrcholů (nejkratší cesty a násobení matic, Floyd- Warshallův algoritmus, Johnsonův algoritmus pro řídké grafy). Maximální toky v sítích (sítě, Ford- Fulkersonova metoda, maximální párování v bipartitních grafech). Datové struktury pro grafové algoritmy (binární haldy, prioritní fronty, binomiální haldy, Fibonacciho haldy, datové struktury pro systémy disjunktních množin).
Literatura
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Informace učitele
http://www.math.muni.cz/~polak
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2001, jaro 2002, jaro 2003, podzim 2003, podzim 2004.