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.