Grafy a algoritmy (FSI-SGA-A)

Akademický rok 2023/2024
Garant: prof. RNDr. Josef Šlapal, CSc.  
Garantující pracoviště: ÚM všechny předměty garantované tímto pracovištěm
Jazyk výuky: angličtina
Cíle předmětu:

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.

Výstupy studia a kompetence:
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ů.
Prerekvizity:
Vyžadovány jsou pouze středoškolské znalosti teorie množin a kombinatoriky.
Obsah předmětu (anotace):

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.

Metody vyučování:

Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách formou řešení příkladů.

Způsob a kritéria hodnocení:

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:

Úč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.

Typ (způsob) výuky:
    Přednáška  13 × 2 hod. nepovinná                  
    Cvičení  13 × 1 hod. povinná                  
Osnova:
    Přednáška

  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í Cvičení budou probíhat v těsné návaznosti na přednášky.
Literatura - základní:
1. Biggs, N.L.: Discrete Mathematics, Oxford Science Publications 1999
3. Zverovich, V.: Modern Applications of Graph Theory, OUP Oxford 2021 
4. Saoub, K.R.: Graph Theory, An Introduction to Proofs, Algorithms, and Applications, Chapman and Hall/CRC 2021
7.

Bondy, J.A., Murty, U.S.R.: Graph Theory, Springer 2008

Literatura - doporučená:
1. Sedláček, J.: Úvod do teorie grafů, Academia, Praha 1977
2. Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990
3. Wallis, W.D.: A Beginner's Guide to Graph Theory, Birkhäuser Boston 2000
5.  Gross, J.L., Yellen, J., Anderson, M.: Graph Theory and its Applications, Chapman and Hall/CRC, 2023
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
N-MAI-A prezenční studium --- bez specializace -- zá,zk 5 Povinný 2 1 Z
N-MAI-P prezenční studium --- bez specializace -- zá,zk 5 Povinný 2 1 Z
N-AIM-A prezenční studium --- bez specializace -- zá,zk 5 Povinný 2 2 Z