Kombinatorika a grafy I - DMI011 (LS 2012/13)

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

Přednáška se koná v úterý od 9:00 v S5.

Doporučená literatura:

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éž.

Co se zatím předneslo:

19. 2. Odhady na faktoriály a kombinační čísla.
26. 2.
Úvod do vytvořujících funkcí.
5. 3.
Pokračování vytvořujících funkcí, Fibonacciho čísla, Catalanova čísla.
12. 3.
Projektivní roviny, latinské čtverce.
19. 3.
Počítání koster grafů (úplný graf, úplný graf bez hrany, odvození rekurence pro speciální grafy).
26. 3.
Počítání dvěma způsoby: Spernerova věta, maximální počet hran v grafu bez trojúhelníku a bez čtyřcyklu.
2. 4.
Toky a řezy v sítích: minimaxová věta, nástin Fordova-Fulkersonova algoritmu.
9. 4.
Vrcholová a hranová souvislost neorientovaných grafů. Mengerova věta a její hranová analogie.
16. 4.
Párování a vrcholové pokrytí v bipartitních grafech: Kőnigova–Egerváryho věta. Systémy různých reprezentantů: Hallova věta. Příklad aplikace: Birkhoffova–von Neumannova věta o bistochastických maticích.
23. 4.
Lemma o uších. Ramseyova věta (ve verzi pro grafy a ve verzi pro barvení dvojic vrcholů více barvami).
30. 4.
Schurova věta. Nekonečná Ramseyova věta pro p-tice.
7. 5.
Princip kompaktnosti, jeho aplikace na barevnost nekonečných grafů. Konečná verze Ramseyovy věty pro p-tice. Kanonická Ramseyova věta pro barvení dvojic.
14. 5.
Samoopravné kódy: základní pojmy a jejich vlastnosti (Hammingova váha, vzdálenost kódu, lineární kód, generující matice, ortogonální doplněk, kontrolní matice).
21. 5.
Hammingovy kódy, Hadamardovy kódy, Singletonův, Hammingův a Gilbertův-Varshamovův odhad na parametry kódů.