Výuka - předmět Teorie grafů, akad. rok 2019/20

Harmonogram:

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

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.