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

Harmonogram:

Výukové týdny: 23.9.2019 - 12.1.2020

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:

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.