Syllabus Diskrétní Matematiky (DMA005) pro I.ročník matematiky
Vyučující: Prof. RNDr. Jaroslav Nešetřil, DrSC. - KAM, Malá Strana III.patro

1) Základní operace s množinami.

2) Typy relací a funkcí.

3) Počet relací na množině, funkcí z X do Y, prostých funkcí, symetrických funkcí.

4) Odhady pro n!.

5) Kombinační číslo, binomická věta.

6) Princip inkluze a exkluze (znění, alespoň jeden důkaz).

7) Řešení problému šatnářky.

8) Latinský obdélník.

9) Odhad počtu latinských čtverců.

10) Částěčně uspořádané množiny.

11) Extremální prvky (minimální, největší apod.), příklady.

12) Lineárně uspořádané množiny, řetezce.

13) Věta o množinoví representaci částečně uspořádaných množin.

14) Věta o lineárním rozšíření (topologické uspořádání).

15) Aplikace na součty reálných čísel (problém lineární střelby).

16) Spernerův problém.

17) Základní pojmy teorie grafů (cesta, kružnice, stupně vrcholů).

18) Souvislost a komponenty.

19) Počet neizomorfních grafů s n vrcholy.

20) Princip sudosti.

21) Neexistence remízy pro hry ve triangulovaném čtverci.

22) Spernerovo lemma o duhových trojúhelnících.

23) Eulerovské množiny.

24) Neexistence mostu v eulerovských množinách.

25) Stromy a lesy.

26) Ekvivalentní charakteristiky stromů.

27) Isomorfismus stromů, střed stromu.

28) Počet stromů na dané množině.

29) Problém minimální kostry.

30) Hladový algoritmus.

31) Prostor cyklů grafů.

32) Systém representantů.