Výuka - předmět Teorie grafů, akad. rok 2022/23
Harmonogram:
| Výukové týdny: | 19.9.2022 - 15.1.2023 | |||
Anotace:
Základy extremální teorie, nejkratší cesty, Floydův algoritmus, algebraické souvislosti. Eulerovské grafy a jejich aplikace. Hamiltonovské grafy a jejich aplikace, Chvátalova věta. Toky v transportních sítích, Ford-Fulkersonova věta, přípustné toky a přípustné cirkulace. Párování v obecných grafech, párování v bipartitních grafech. Vrcholové a hranové pokrytí, nezávislé množiny. Kliky v grafu, barevnost grafu. Rovinné grafy. Prostor kružnic a prosto řezů, jiná charakterizace rovinných grafů.
Obsah přednášky bude uzpůsoben znalostem zapsaných studentů.
Literatura:
- Reinhard Diestel: Graph Theory, Springer-Verlag, New York, 1997
- Jiří Demel: Grafy a jejich aplikace, Academia, Praha, 2002
- M.N.S. Swamy, K. Thulasiraman: Graphs, Networks, and Algorithms, Part 1, Graph Theory, John Wiley & Sons, New York, 1981
Přednášky - Přednášky.
Cvičení je nahrazeno samostatnou prací, která spočívá hlavně ve vypracování domácích úkolů. Zkouška má podobu rozpravy nad domácími úkoly.
Domácí úlohy - Text domácích úloh.