Základy kombinatoriky a teorie grafů

Sylabus

Základy NP-úplnosti - nedeterministické Turingovy stroje, Cookova věta, základní NP-úplné problémy (3-splnitelnost, Hamiltonovská kružnice, nezávislá množina, exaktní pokrytí).

Odhady faktoriálu a binomických koeficientů.

Princip inkluze a exkluze a jeho aplikace (šatnářka).

Vytvořující funkce a jejich aplikace.

Konečné projektivní roviny, latinské čtverce a jejich ortogononalita.

Hallova věta a aplikace.

Toky v sítích. k-souvislost grafů, Mengerovy věty pro (ne)orientovane grafy ve verzích pro vrcholy a hrany.

Základni Ramseyovy věty, věta pro p-tice, Schurova věta a další aplikace.

Anotace

Úvodní kurs, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce. Doporučeno pro zaměření Matematické struktury na Obecné matematice a pro obor MMIB.