Seznam všech definic, vět a důležitých příkladů z přednášky, které požaduji u zkoušky.
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 mezi množinami, relace na množině
Příklady relací: prázdná, univerzální, diagonální (množina všech dvojic (x,x))
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 (Lemma 2)
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 (Lemma 5)
Řetězec a antiřetězec
Věta o dlouhém a širokém
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
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ň
*Silná a slabá souvislost orientovaných grafů
Skóre grafu
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ý.
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
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. Věta 5
Barevnost ≥ klikovost Pozorování 2
d-degenerované grafy jsou (d+1)-obarvitelné (aka "Princip barvení indukcí"), z toho vyplývá...
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ě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é (jsou to dvě různé věci)
*Součin pravděpodobnostních prostorů (bod 23)
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
Čebyševova nerovnost
Velikost řezu v grafu: střední hodnota, existuje velký řez