M015 Grafové algoritmy

Fakulta informatiky
léto 1998
Rozsah
2/1. 3 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
doc. RNDr. Libor Polák, CSc. (přednášející)
Garance
Kontaktní osoba: doc. RNDr. Libor Polák, CSc.
Předpoklady
Doporučeno je absolvovat M010 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
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).
Předmět je zařazen také v obdobích léto 1996, léto 1997, jaro 1999, jaro 2000, jaro 2001, jaro 2002.