Grafy a algoritmy (FSI-SGA-A)

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

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ů.

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.

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ě

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