Diskrétní matematika

Sylabus

Pojem množiny (Cantor), jazyk teorie množin, formule.

Popis množiny výčtem nebo jako množiny prvků "dané vlastnosti".

Základní operace s množinami (vč. potence a sumy) a jejich vlastnosti.

Kartézský součin, (binární) relace, skládání relací.

Funkce, funkce prostá, na, bijekce.

Vlastnosti relací (reflexivita, symetrie, ...).

Relace ekvivalence na množině, rozklad množiny, vzájemný vztah, příklady.

Kombinatorické počítání.

Počet zobrazení (prostých zobrazení) n-prvkové do m-prvkové množiny, počet podmnožin n-prvkové množiny.

Variace, permutace, kombinace.

Kombinační čísla, binomická věta.

Princip inkluze a exkluze.

Asymptotické odhady faktoriálu a kombinačních čísel.

Definice grafu, základní terminologie, izomorfismus grafů.

Stupeň vrcholu, princip sudosti, skóre grafu.

Cesty v grafu, souvislost, komponenty.

Metrika v grafu a pojmy z ní odvozené.

Stromy, jejich charakterizace a vlastnosti, počet stromů na dané množině.

Isomorfismus stromů, kódování stromů.

Kostra grafu, hledání minimální kostry.

Uspořádání, lineární uspořádání, největší/nejmenší, maximální/minimální prvek, řetězec/antiřetězec, supremum/infimum, příklady.

Existence minimálního prvku a věta o lineárním rozšíření pro konečné množiny.

Isomorfismus množin vzhledem k relacím.

Reprezentace částečného uspořádání pomoci inkluze.

Dobré uspořádání, princip indukce pro přirozená čísla.

Eulerovské tahy.

Eulerovské podgrafy a jejich popis pomocí vektorových prostorů (prostor cyklů a řezů).

Rovinné grafy.

Nakreslení grafu do roviny.

Eulerova formule a její důsledky.

Obarvení rovinného grafu pěti barvami.

Rozšiřující témata:

Ramseyova věta pro grafy, vícebarevná Ramseyova věta.

Dolní odhad Ramseyových čísel.

Anotace

Základní přednáška z diskrétní matematiky pro všechny odborné obory bakalářského programu Matematika.