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

Harmonogram:

Výukové týdny: 2.10.2017 - 14.1.2018

Anotace:

Základní pojmy teorie grafů. Stromy, jejich charakterizace, minimální kostry. Silně souvislé grafy, silně souvislé komponenty, prohledávání, kořenové stromy. 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.

Homeworks - Homeworks in English.