Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky. (Typicky se nové informace budou objevovat pár desítek minut až pár jednotek hodin po přednášce, občas možná až po víkendu.)
Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.
Pokud chcete mít představu, jak asi bude přednáška probíhat, můžete se podívat na její předchozí běh.
Doporučená literatura: J. Matoušek, J. Nešetřil, Kapitoly z Diskrétní Matematiky
Erdős-Szekerésovo lemma/věta, Lemma 2.4.6, podle vydání 2009 (cvičení 10 v 6.2 ve vydání z roku 2000; velmi doporučuju čerpat z novější verze kapitol, budete-li mít možnost).
Definice náhodného grafu, Definice 10.2.6 podle vydání 2009 (Definice 9.2.6. ve vydání 2000). Pochopení může také výrazně pomoci se podívat na úlohu 10.2.7 (9.2.7 ve vydání 2000), ale nemá význam se učit řešení úlohy nazpaměť.
Existence velkých bipartitních podgrafů, Věta 10.4.1 podle vydání 2009 (9.4.1 ve vydání 2000).
Další upozornění:
Vzorovou písemku naleznete zde. Bodování pro tuto konkrétní písemku by bylo 1: 23-30b; 2: 20-22b; 3: 16-19b; 3-: 8-15b; 4: 0-7b. (Pro jiné písemky může být bodování mírně upraveno podle obtížnosti písemky.)
Přednáška 1 (6. 10.) Motivace. Základní pojmy a značení, množiny. Důkaz matematickou indukcí. Kartézský součin. Relace: reflexivita, symetrie, tranzitivita; relace ekvivalence a třídy ekvivalence. Tvrzení o rozkladu na třídy ekvivalence.
Přednáška 2 (13. 10.) Funkce: definice, prostá funkce, funkce na, bijekce, inverzní funkce a skládání funkcí. (Poznámky o inverzní relaci a skládání relací). Částečná uspořádání, porovnatelné prvky, řetězce, antiřetězce, Hasseův diagram. Maximální, největší, minimální a nejmenší prvek. Věta o dlouhém a širokém.
Přednáška 3 (20. 10.) Kombinatorické počítání: tvrzení o počtu funkcí, počtu podmnožin, počtu sudých a lichých podmnožin, počtu prostých zobrazení. Permutace, počet permutací (faktoriál), rozklad permutací na cykly. Kombinační čísla, množina N nad k, tvrzení o počtu k-prvkových podmnožin. Motivační příklad na princip inkluze a exkluze.
Přednáška 4 (27. 10.) Princip inkluze a exkluze, znění a důkaz. Problém šatnářky a počet permutací bez pevného bodu. Základy diskrétní pravděpodobnosti: pravděpodobnostní prostor (neúplná definice), diskrétní pravděpodobnostní prostor, elementární jev, jev, příklady pravděpodobnostních prostorů.
Přednáška 5 (3. 11.) Podmíněná pravděpodobnost, spolehlivost testu jako příklad na podmíněnou pravděpodobnost, Bayesova věta. Nezávislé jevy. Součin pravděpodobnostních prostorů. Náhodná veličina, střední hodnota. Indikátor jevu. Příklad: střední hodnota počtu 1 v náhodné posloupnosti 0 a 1 délky n, z definice a přes indikátory.
Přednáška 6 (10. 11.) Nezávislost náhodných veličin. Graf. Důležité grafy: úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf. Izomorfismus grafů. Sousednost (incidence), podgraf a indukovaný podgraf. Sled, tah a cesta v grafu. Relace ~ vyjadřující existenci cesty mezi dvěma vrcholy je ekvivalence. Souvislost grafu a komponenty souvislosti. Matice sousednosti.
Přednáška 7 (24. 11.) Věta o počtu sledů. Stupeň vrcholu a skóre grafu. Princip sudosti a počet vrcholů lichého stupně. Věta o skóre. Eulerovské grafy. Charakterizace eulerovských grafů pomocí souvislosti a sudosti stupňů vrcholů.
Přednáška 8 (1. 12.) Definice orientovaného grafu. Tah v orientovaném grafu, eulerovské orientované grafy. Vstupní a výstupní stupeň vrcholu v orientovaném grafu, silná a slabá souvislost. Charakterizace orientovaných eulerovských grafů (důkaz se předpokládá na cvičeních). Aplikace eulerovských grafů na existenci cycklických posloupností nul a jedniček obsahujících, pro dané k všechny možné k-tice po sobě jdoucích nul a jedniček právě jednou. Stromy, definice stromu a listu. Lemma o existenci listů a lemma o trhání listů (důkaz zatím pouze jedné implikace).
Přednáška 9 (8. 12.) Druhá implikace lemma o trhání listů. Věta o ekvivalentních charakterizacích stromů. Kostra grafu. Graf má kostru, právě když je souvislý. Definice oblouku v rovině.
Přednáška 10 (15. 12.) Drobná oprava definice oblouku; oblouková souvislost. Nakreslení grafu, rovinné nakreslení, rovinný graf. Eulerův vzorec pro rovinné grafy. Tvrzení o doplnění rovinného grafu na triangulaci. Důsledek o maximálním počtu hran rovinného grafu. Důsledek důsledku, každý rovinný graf obsahuje vrchol stupně nejvýše 5.
Přednáška 11 (22. 12.) Hlavně pro počítání příkladů: stupeň stěny; součet stupňǔ stěn je dvakrát počet hran; rovinný graf bez trojúhelníků s n vrcholy má nejvýše 2n-4 hran; duální graf (pouze obrázkem). Barvení grafu: obarvení k barvami, chromatické číslo. k-degnerovaný graf. Tvrzení o chrom. čísle k-degnerovaného grafu. Věta o 4 barvách (bez dk.); věta o 6 barvách jako důsledek tvrzení. Věta o 5 barvách (s důkazem).
Přednáška 12 (5. 1.) Erdős-Szekerésova věta (dva důkazy). Pravděpodobnostní důkazy: hledání velkého bipartitního podgrafu; náhodný graf G(n,p) a konkrétní příklad využití pro existenci grafu s 2^50 vrcholy bez nezávisle množiny velikosti 100 či úplného podgrafu velikosti 100. (Motivováno Ramseyovou větou.)