Kombinatorika a grafy I - NDMI011 (LS 2014/15)

přednášející V. Jelínek

Přednáška se koná v pátek od 9:00 v S3.

• Odhady na n!, (n nad k), (2n nad n). Tato "přednáška" proběhla na prvním cvičení.
• 20. 2.: Vytvořující funkce, zobecněná binomická věta, odvození vytvořující funkce pro Fibonacciho čísla.
• 27. 2.: Rozklad racionální funkce na parciální zlomky a jeho využití pro výpočet koeficientů mocninných řad. Aplikace: výpočet vzorečku pro n-tý člen posloupnosti určené pomocí (homogenní, lineární) rekurence s konstantními koeficienty. Výpočet počtu binárních zakořeněných stromů pomocí vytvořujících funkcí, Catalanova čísla.
• 6. 3.: Projektivní roviny, jejich dualita, incidenční graf, základní vlastnosti konečných projektivních rovin. Latinské čtverce, jejich ortogonalita.
• 13. 3.: Odhad na počet navzájem ortogonálních latinských čtverců, souvislost latinských čtverců a projektivních rovin. Toky v sítích, řezy, zlepšující cesty. Věta o tom, že velikost maximálního toku je rovna kapacitě minimálního řezu.
• 20. 3.: Párování a vrcholové pokrytí: souvislost mezi jejich velikostmi. Kőnigova–Egerváryho věta. Systémy různých reprezentantů a jejich souvislost s párováním v grafu incidence. Hallova věta. Lemma o vybírání kladných prvků v bistochastické matici.
• 27. 3.: Vrcholová a hranová k-souvislost grafů. Mengerovy věty pro vrcholovou a hranovou k-souvislost.
• 3. 4.: Lemma o uších pro vrcholově 2-souvislé grafy. Cayleyho vzorec pro počet koster úplného grafu (dokázaný pomocí povykosů). Důsledek: počet koster úplného grafu (ne)obsahujících danou hranu.
• 10. 4.: Spernerova věta o velikosti nezávislého systému množin. Horní odhad na počet hran grafu neobsahujícího kružnici délky 4. Obdobná úloha pro kružnici délky 3.
• 17. 4.: Ramseyovy věty: symetrická a nesymetrická verze pro grafy, verze pro barvení dvojic vrcholů konečným počtem barev.
• 24. 4.: Ramseyovy věty pro barvení p-tic, v konečné a nekonečné verzi (dokázalo se, že nekonečná verze implikuje konečnou a že nekonečná verze platí pro p nejvýš 2). Kőnigovo lemma, jeho použití k důkazu, že spočetný nekonečný graf lze obarvit b barvami, pokud každý jeho konečný podgraf lze obarvit b barvami.
• 15. 5.: Samoopravné kódy - základní pojmy: Hammingova váha, Hammingova vzdálenost, (n,k,d)-kód, kódování, dekódování, lineární kód, ortogonální doplněk (=duální kód), generující matice a její využití při kódování, kontrolní matice.
• 22. 5.: Užití kontrolní matice při rozpoznávání kódových slov, vztah mezi sloupci kontrolní matice a minimální vzdáleností kódu. Hammingovy kódy, jejich dekódování. Odhady na parametry kódů: Singletonův, Hammingův, Gilbertův-Varshamovův.
  

Doporučená literatura:

• J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky, Karolinum 2000 (dotisk 2002, 2007 a 2009, předchozí vydání MatfyzPress 1996). Ve starším vydání knihy je několik chyb, pozor na ně.
• Skriptíčka T. Vally a J. Matouška, ke stažení zde.
• Učební text T. Kaisera k přednášce o samoopravných kódech, ke stažení zde.
  

Cvičení a zápočty: Informace o zápočtech se dozvíte od svých cvičících.

Zkoušky: Přihlašování pomocí SISu, termíny tamtéž. Pozor, nejspíš budu celé září v cizině, takže v září termíny zkoušek nebudou.