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

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/2)n

Odhad kombinačního čísla: (n/k)k ≤ C(n,k) ≤ nk

Odhad prostředního kombinačníhco čí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ů

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í (nebo jednovrcholový), graf neobsahuje lichou kružnici.

k-degenerovanost

Stromy jsou 1-degenerované, rovinné grafy 5-degenerované, grafy s maximálním stupněm Δ jsou Δ-degenerované.

k-degenerované grafy mají barevnost nejvýše k+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

Markovova nerovnost

Velikost řezu v grafu: střední hodnota, existuje velký řez, pravděpodobnostní algoritmus

Různé

Erdősovo-Szekeresovo lemma o monotónních podposloupnostech

Existence de Bruijnovy posloupnosti (konstrukce pomocí orientovaných eulerovských tahů)

Stránku spravuje Martin Mareš