Požadavky ke zkoušce z DM
Seznam všech definic, vět a důležitých příkladů z přednášky, které požaduji u zkoušky.
Úvod
Technika důkazu indukcí a sporem
Operace s čísly: sumy, produkty, horní a dolní celá část
Množinové operace: rovnost, inkluze, sjednocení, průnik, rozdíl, symetrická diference, potence (množina podmnožin), mohutnost (počet prvků)
Uspořádané k-tice a kartézský součin
Relace
Relace mezi množinami, relace na množině
Příklady relací: prázdná, univerzální, diagonální
Operace s relacemi: inverze, skládání
Funkce (zobrazení) a jejich druhy: prosté (injektivní), na (surjektivní), vzájemně jednoznačné (bijektivní)
Vlastnosti relací: reflexivita, symetrie, antisymetrie, transitivita
Ekvivalence, ekvivalenční třída, rozklad množiny
Vztah mezi ekvivalencemi a rozklady
Uspořádání
Uspořádání částečné a lineární, uspořádaná množina, ostré uspořádání
Příklady uspořádání: dělitelnost, inkluze podmnožin, lexikografické
Hasseův diagram, relace bezprostředního předchůdce
Minimální/maximální a nejmenší/největší prvek
Konečná neprázdná uspořádaná množina má minimální a maximální prvek
Řetězec a antiřetězec
Kombinatorické počítání
Počet funkcí mezi množinami
Počet prostých funkcí mezi množinami
Charakteristická funkce podmnožiny
Počet všech podmnožin
Počet podmnožin sudé a liché velikosti
Počet permutací na množině
Počet uspořádaných k-tic bez opakování a k-prvkových podmnožin
Notace pro množinu všech k-prvkových podmnožin
Kombinační číslo (binomický koeficient), Pascalův trojúhelník
Základní vlastnosti kombinačních čísel
Binomická věta
Princip inkluze a exkluze
Problém šatnářky: počet permutací bez pevného bodu
Odhad faktoriálu: nn/2 ≤ n! ≤ ((n+1)/2)n
Odhad kombinačního čísla: (n/k)k ≤ C(n,k) ≤ nk
Odhad prostředního kombinačního čísla: 4n/(2n+1) ≤ C(2n,n) ≤ 4n
Grafy
Graf, vrchol, hrana, V(G), E(G)
Standardní grafy: úplný, prázdný, cesta, kružnice
Bipartitní graf, úplný bipartitní graf
Isomorfismus grafů
Stupeň vrcholu, k-regulární graf, skóre grafu
Vztah mezi součtem stupňů a počtem hran, princip sudosti
Podgraf, indukovaný podgraf
Cesta, kružnice, sled a tah v grafu
Souvislý graf, relace dosažitelnosti (ekvivalence), komponenty souvislosti
Dosažitelnost sledem je totéž jako dosažitelnost cestou
Matice sousednosti
Počet sledů délky k lze získat z k-té mocniny matice sousednosti
Vzdálenost v grafu (grafová metrika)
Trojúhelníková nerovnost pro vzdálenost
Grafové operace: přidání/odebrání vrcholu/hrany, dělení hrany, kontrakce hrany
Otevřený a uzavřený eulerovský tah
Věta o existenci uzavřeného eulerovského tahu
Orientovaný graf, podkladový graf, vstupní a výstupní stupeň, vyváženost vrcholu
Silná a slabá souvislost orientovaných grafů
Uzavřené eulerovské tahy v orientovaných grafech
Stromy
Strom, les, list
Lemma o koncovém vrcholu
Je-li l list grafu G, pak G je strom, právě když G-l je strom.
Pět ekvivalentních charakteristik stromu
Kostra grafu
Graf má kostru, právě když je souvislý.
Rovinné kreslení grafů
Oblouk, topologická kružnice, rovinné nakreslení grafu
Oblouková souvislost a její komponenty, stěna nakreslení
Rovinný graf, topologický graf
Jordanova věta o kružnici (bez důkazu)
K5 a K3,3 nejsou rovinné.
Hranice stěny je nakreslením uzavřeného sledu.
Stereografická projekce
Graf jde nakreslit do roviny, právě když jde nakreslit na sféru.
Vnější stěnu lze zvolit.
Kreslení na další plochy: válcová plocha, torus
Kuratowského věta (bez důkazu)
Eulerova formule pro souvislé rovinné grafy (v+f=e+2)
Maximální rovinný graf je triangulace.
Maximální počet hran rovinného grafu
V rovinném grafu existuje vrchol stupně nejvýše 5.
Počet hran a vrchol nízkého stupně v rovinných grafech bez trojúhelníků
Duální multigraf
Barvení grafů
Obarvení grafu k barvami, barevnost
Barevnost úplných grafů, cest a kružnic
Ekvivalentní tvrzení: graf má barevnost nejvýše 2, graf je bipartitní, graf neobsahuje lichou kružnici.
Barevnost ≥ klikovost
Princip barvení indukcí: stromy jsou 2-obarvitelné, rovinné grafy 6-obarvitelné
Barevnost ≤ maximální stupeň + 1
Věta o 5 barvách
Věta o 4 barvách (bez důkazu)
Pravděpodobnost
Pravděpodobnostní prostor diskrétní, konečný, klasický
Jev elementární, jev složený, pravděpodobnost jevu
Jev se také dá popsat logickou formulí.
Bertrandův paradox s kartičkami
Podmíněná pravděpodobnost
Věta o úplné pravděpodobnosti
Bayesova věta
Jevy nezávislé a po dvou nezávislé
Součin pravděpodobnostních prostorů, projekce
Náhodná veličina
Logické formule s náhodnými veličinami dávají jevy.
Střední hodnota
Věta o linearitě střední hodnoty
Indikátor náhodného jevu
Použití indikátorů k výpočtu střední hodnoty