ÚVOD / Studijní obory / Sylaby / Grafové algoritmy

Grafové algoritmy

Předmět tematicky volně navazuje na látku probíranou v rámci předmětu "Základy návrhu a optimalizace algoritmů" a "Matematika 2". Zaměřovat se bude hlavně na problematiku z oblasti teorie grafů, tedy především vůbec na způsoby reprezentace grafu samotného v paměti počítače a následně pak na grafové algoritmy, například průchod grafu (do hloubky, do šířky), hledání nejkratší cesty v grafu nebo hledání minimální kostry grafu, apod. Důraz bude kladen také na praktické procvičení vybraných algoritmů a jejich implementaci v jazyce Ruby. Cílem předmětu je ukázat, jaké jsou možnosti využití grafů a grafových algoritmů v praxi.

Sylabus předmětu

  1. Grafy – pojem grafu a základní tvrzení grafů se týkajících (opakování z MA2), reprezentace grafů v paměti počítače.
  2. Stromy – pojem stromu a základní tvrzení stromů se týkajících (opakování z MA2), isomorfismus stromů.
  3. Průchody grafem – průchod grafem do hloubky, průchod grafem do šířky, hledání nejkratší cesty v grafu (Dijkstrův algoritmus).
  4. Hledání minimální kostry grafu – Kruskalův hladový algoritmus, Jarníkův algoritmus, Borůvkův algoritmus.
  5. Barvení grafu – představení problému, algoritmy pro (neoptimální) obarvení grafu: naivní algoritmus, Welsh-Powellův algoritmus, DSATUR, RLF.
  6. Orientované grafy – základní definice a tvrzení, topologické setřídění vrcholů.

Organizace výuky

Prezenční forma

Výuka probíhá v 6 přednáškách a 6 seminářích po 1,5 hod.

Kombinovaná forma

Kombinovaná forma není v tomto kurzu zavedena, tento kurz je pro kombinované studenty veden prezenční formou.

Doporučená literatura

Základní učební texty a pomůcky

  • Učební texty k předmětu Grafové algoritmy (intranetová učební pomůcka), Unicorn College
  • MATOUŠEK, J., NEŠETŘIL, J.: Kapitoly z diskrétní matematiky, třetí vydání, Karolinum, 2007.
  • DIESTEL, R.: Graph Theory, 4th edition, Springer, 2012.

Doplňující a rozšiřující učební texty

  • BOLLOBÁS, B.: Modern Graph Theory, Corrected Edition, Springer, 2013.