Předmět Základy kombinatoriky a teorie grafů (NMIN331)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NMIN331 - Základy kombinatoriky a teorie grafů, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
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.
Literatura
Literatura dle doporučení učitele.
Garant
doc. RNDr. Pavel Valtr, Dr.