Sylabus k prednasce "Diskretni matematika"
(Jan Kratochvil, Jiri Matousek, KAM)
Organizacni poznamky.
Cviceni je nedilnou soucasti predmetu, a
nektera jednodussi temata budou probirana pouze v nich.
Vety probrane na prednasce se u zkousky pozaduji i s dukazem,
neni-li na prednasce receno jinak.
- Zakladni pojmy:
operace s mnozinami;
zobrazeni, zobrazeni proste, na, bijekce,
permutace, skladani zobrazeni; relace, vlastnosti
relaci (reflexivita, symetrie, tranzitivita), ekvivalence;
zapisy sum a soucinu; dukaz matematickou indukci;
castecne usporadani, linearni usporadani,
priklady usporadanych mnozin; zapis $O()$, $\Omega()$, $o()$
pro asymptoticke porovnavani rychlosti rustu funkci.
- Kombinatoricke pocitani: Funkce faktorial a
binomicky koeficient, jejich kombinatoricky vyznam, binomicka
veta, nektere vzorce pro binomicke koeficienty;
princip inkluze a exkluze (slovni formulace,
zapis formuli, dukaz), pouziti inkluze a exkluze (problem
satnarky).
- Odhady:
jednoduche odhady funkce faktorial a binomickeho
koeficientu.
- Zaklady teorie grafu:
terminologie (neorientovany graf, orientovany graf, stupen vrcholu, uplny graf,podgraf, cesta, sled, tah, souvisly graf, komponenta, kruznice,
bipartitni graf); isomorfismus grafu;
algoritmus pro hledani nejkratsi cesty v grafu;
eulerovsky tah, charakterizace grafu majicich eulerovsky tah
pomoci stupnu;
dvousouvisle grafy, blokovy rozklad grafu, lemma o usich.
- Stromy: nekolik ekvivalentnich definic stromu;
kostra; graf s ohodnocenymi hranami, minimalni kostra, hladovy
algoritmus (formulace a dukaz spravnosti).
- Rovinne grafy:
pojem rovinneho grafu; Jordanova veta
o kruznici (formulace);
stena nakresleni, Eulerova relace (souvislost poctu vrchlou, hran
a sten), maximalni pocet hran
rovinneho grafu, triangulace, graf mnohostenu, platonska telesa.
- Priklady slozitejsich dukazu pocitanim dvema zpusoby:
nemoznost remizy ve hre HEX;
maximalni pocet hran grafu neobsahujiciho K_{2,2};
Spernerova veta (maximalni pocet neporovnatelnych podmnozin
n -prvkove mnoziny).
- Konecne projektivni roviny a latinske ctverce:
axiomy projektivni roviny radu n, priklad radu 2 (Fanova
rovina), pocet bodu a primek konecne projektivni roviny; latinsky
ctverec, ortogonalni latinske ctverce, souvislost s konstrukci
konecnych projektivnich rovin (jen princip).