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.

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

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. Dále budou studenti seznámeni s bipartitními grafy, s problémy 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, které teorie grafů nachází především v  technických vědách. Důraz bude kladen na aplikace v informatice, optimalizaci, teorii řízení a  operačním výzkumu.

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