Sylabus
Značení, motivační úlohy, co je důkaz, důkaz indukcí.
Kombinatorika:
- Relace: zobrazení (funkce, permutace), ekvivalence.
- Částečné uspořádání: řetězce a antiřetězce, věta o dlouhém a širokém.
- Kombinatorické počítání: počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých zobrazení, permutací.
- Binomická věta. Odhady faktoriálu a binomických koeficientů.
- Princip inkluze a exkluze a jeho aplikace (šatnářka).
Pravděpodobnost:
- Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy).
- Nezávislé jevy, podmíněná pravděpodobnost.
- Náhodná veličina: distribuční funkce, střední hodnota, linearita, základní diskrétní pravděpodobnostní rozdělení.
Teorie grafů:
- Základní pojmy: úplný graf, úplný bipartitní graf, cyklus, cesta, stupeň vrcholu, podgraf, izomorfismus.
- Princip sudosti.
- Eulerovské grafy: tah, sled, charakterizace, též orientovaný případ, silná a slabá souvislost.
- Stromy: různé charakterizace, existence listu.
- Rovinné grafy: Eulerova formule, maximální počet hran.
- Barevnost grafu: charakterizace bipartitních grafů, d-degenerované grafy, věta o pěti barvách pro rovinné grafy (Kempeho řetězce).
Rozšiřující témata:
- Erdősovo-Szekeresovo lemma o monotónní podposloupnosti.
- Pravděpodobnostní důkaz (např. existence 3-paradoxního turnaje).
- Skóre grafu.
- Platónská tělesa.
- Spernerovo lemma, aplikace na hru HEX.
Anotace
Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).