Detail předmětu

Grafy a algoritmy

FSI-SGA-AAk. rok: 2023/2024

V kurzu budou studenti seznámeni se základy teorie grafů a s některými algoritmy, které jsou na této teorii založeny. Po zavedení základních pojmů budou diskutovány klasické problémy jako Eulerův tah, Hamiltonova kružnice, vybarvování uzlů, planarita apod. Budou také studovány stromy a algoritmy pro hledání minimální kostry. Studenti budou seznámeni s bipartitními grafy, s problémem párování a hledání nejkratší cesty. Pozornost bude věnována rovněž orientovaným grafům včetně algoritmů pro hledání kritické cesty.  Nakonec bude pojednáno o sítích a tocích v nich. Výklad bude veden se zřetelem na aplikace teorie grafů, které zasahují do mnoha oblastí života společnosti. Důraz bude přitom kladen na aplikace v informatice, optimalizaci, teorii řízení a  operačním výzkumu.

Jazyk výuky

angličtina

Počet kreditů

5

Garant předmětu

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

Ústav matematiky (ÚM)

Vstupní znalosti

Vyžadovány jsou pouze středoškolské znalosti teorie množin a kombinatoriky.

Pravidla hodnocení a ukončení předmětu

Podmínkou pro zápočet je aktivní účast ve cvičeních a prokázání znalostí při písemných testech, které budou průběžně konány. V písemné části zkoušky je třeba prokázat schopnost řešit zadaný problém na základě získaných vědomostí, v její ústní části pan zvládnutí probrané teorie.


Účast na cvičeních je povinná a vyučující ji bude pravidelně kontrolovat. V případě omluvené nepřítomnosti student obdrží příklady k samostatnému vypracování tak, aby mohl zameškanou látku zvládnout.

Učební cíle

Cílem kurzu je seznámit studenty s teorií grafů a na ní založenými
algoritmy, které jsou často používány k řešení problémů v technických i mnoha jiných oborech.


Studenti získají základní znalosti z teorie grafů a grafových algoritmů.
Budou tak schopni modelovat pomocí grafů různé problémy z praxe a ty pak
řešit pomocí osvojených algoritmů.

Základní literatura

Biggs, N.L.: Discrete Mathematics, Oxford Science Publications 1999 (EN)
Bondy, J.A., Murty, U.S.R.: Graph Theory, Springer 2008 (EN)
Saoub, K.R.: Graph Theory, An Introduction to Proofs, Algorithms, and Applications, Chapman and Hall/CRC 2021 (EN)
Zverovich, V.: Modern Applications of Graph Theory, OUP Oxford 2021  (EN)

Doporučená literatura

 Gross, J.L., Yellen, J., Anderson, M.: Graph Theory and its Applications, Chapman and Hall/CRC, 2023 (EN)
Sedláček, J.: Úvod do teorie grafů, Academia, Praha 1977 (CS)
Wallis, W.D.: A Beginner's Guide to Graph Theory, Birkhäuser Boston 2000 (EN)
Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990 (EN)

Elearning

eLearning: aktuální otevřený kurz

Zařazení předmětu ve studijních plánech

  • Program N-AIM-A magisterský navazující 2 ročník, zimní semestr, povinný
  • Program N-MAI-A magisterský navazující 1 ročník, zimní semestr, povinný
  • Program N-MAI-P magisterský navazující 1 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Michael Joseph Lieberman, Ph.D.

Osnova

  1. Základní pojmy
  2. Tahy, cesty a kružnice
  3. Stromy a kostry
  4. Vybarvování uzlů
  5. Planarita
  6. Třídicí algoritmy
  7. Hledání nejkratší cesty
  8. Vybarvování hran
  9. Bipartitní grafy
  10. Párování
  11. Orientované grafy
  12. Problém kritické cesty
  13. Toky a sítě

Cvičení

13 hod., povinná

Vyučující / Lektor

Michael Joseph Lieberman, Ph.D.

Osnova

Cvičení budou probíhat v těsné návaznosti na přednášky.

Elearning

eLearning: aktuální otevřený kurz