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
parametry α a ω
O Dlouhém a Širokém
Erdősovo-Szekeresovo lemma o monotónních podposloupnostech
Kombinatorické počítání
Počet funkcí mezi množinami
Počet prostých funkcí mezi množinami
Klesající mocnina
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
Věta o skóre
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ů
Rovinné nakreslení grafu a jeho stěny (neformálně)
Rovinný graf, topologický graf
K5 a K3,3 nejsou rovinné.
Hranice stěny je nakreslením uzavřeného sledu (bez důkazu).
Stereografická projekce
Graf jde nakreslit do roviny, právě když jde nakreslit na sféru.
Vnější stěnu lze zvolit.
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ů
Klasifikace platónských těles pomocí rovinných grafů
Barvení grafů
Převod barvení mapy na barvení grafu pomocí duality
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 k nezávislé
Jevy, které jsou po 2 nezávislé, ale po 3 už ne
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
Markovova nerovnost
Velikost řezu v grafu: střední hodnota, existuje velký řez, pravděpodobnostní algoritmus