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
Techniky důkazu: obměnou, sporem, principem holubníku, indukcí
Součet konečné aritmetické a geometrické řady
Značení pro operace s čísly: sumy, produkty, horní a dolní celá část, dělitelnost
Značení pro množinové operace: rovnost, inkluze, sjednocení, průnik, rozdíl, potence (množina podmnožin), mohutnost (počet prvků)
Uspořádané k-tice a kartézský součin
Kombinatorické počítání
Počet řetězců nad danou abecedou
Počet řetězců bez opakování znaků
Počet permutací na množině
Počet (prostých) funkcí mezi množinami
Charakteristická posloupnost/funkce podmnožiny
Klesající mocnina
Počet všech podmnožin
Počet podmnožin sudé a liché velikosti
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
Pravděpodobnost
Pravděpodobnostní prostor diskrétní, konečný, klasický
Jev elementární, jev složený, pravděpodobnost jevu
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ů
Pokus s barevnými kartičkami kartičkami
Podmíněná pravděpodobnost
Věta o rozboru případů (o úplné pravděpodobnosti)
Bayesova věta
Grafy
Graf, vrchol, hrana, V(G), E(G)
Standardní grafy: úplný, prázdný, cesta, kružnice
Bipartitní graf, úplný bipartitní graf
Stupeň vrcholu, k-regulární graf
Vztah mezi součtem stupňů a počtem hran, princip sudosti
Podgraf, indukovaný podgraf
Izomorfismus grafů, automorfismus
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
Otevřený a uzavřený eulerovský tah
Věta o existenci uzavřeného eulerovského tahu
Orientovaný graf, vstupní a výstupní stupeň, vyváženost vrcholu
Silná a slabá souvislost orientovaných grafů
Uzavřené eulerovské tahy v orientovaných grafech
Charakterizace extremálních grafů bez trojúhelníku (jen pro sudý počet vrcholů)
Stromy
Strom, les, list
Graf je minimální souvislý, právě když je souvislý bez kružnic.
Lemma o koncovém vrcholu
Je-li l list grafu G, pak G je strom, právě když G-l je strom.
Graf je strom, právě když je souvislý a |E|=|V|-1.
Šest ekvivalentních charakteristik stromu
Kostra grafu
Relace
Relace mezi množinami, relace na množině
Příklady relací: prázdná, univerzální, identita (diagonální)
Operace s relacemi: inverze, skládání
Zobrazování relací: tabulka, orientovaný graf, bipartitní graf
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
Řetězec a antiřetězec
Horní/dolní závora a supremum/infimum
Konečná neprázdná uspořádaná množina má minimální a maximální prvek.
Částečné uspořádání na konečné množině má lineární rozšíření.
Topologické uspořádání orientovaného grafu
Izomorfismus uspořádání
Vnoření uspořádání
Každé uspořádání lze vnořit do inkluze.
Rovinné grafy
Rovinné nakreslení grafu a jeho stěny (neformálně)
Rovinný graf, topologický rovinný 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.
Kreslení na další plochy: válcová plocha, torus
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ů
Dělení a kontrakce hrany zachovávají rovinnost.
Kuratowského věta (bez důkazu)
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.
Klikovost grafu
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)
Ramseyovy věty
Ramseyova věta pro grafy
Ramseyova čísla R(k), R(k,l)
Dolní odhad R(n) ≥ 2k/2 (důkaz pravděpodobnostní metodou)
Vícebarevná Ramseyova věta
Nekonečná Ramseyova věta (spočetná verze)