====== Přednáška z Kombinatoriky a grafů I 2020/21 ======

Přednáším Kombinatoriku a grafy 1 ([[https://is.cuni.cz/studium/predmety/index.php?id=ba8eda93f7839482990ce4ad5279c960&tid=&do=predmet&kod=NDMI011&skr=2020&fak=11320|NDMI011]]) každé úterý v 10:40.

Pokud máte dotaz, který můžete vznést veřejně, nejlepší prostor je tým v MS Teams. Pokud v něm nejste, napište mi email. Pokud máte soukromý dotaz, napište mi e-mail na adresu ''koutecky@iuuk.mff.cuni.cz'' a do předmětu uveďte text ''[KG1]''. Až bude probíhat výuka osobně, jste též vítáni v mé pracovně S326.

Další materiály doplním v průběhu semestru.



{{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
^ datum ^ co se přednášelo [zdroj] ^
| 29. 9. | Odhady faktoriálu - jednoduchý, lepší pomocí indukce a integrování, zmínka Stirlingovy formule. Odhad $\binom{n}{k}$ jako $n^k$ když $k \ll n$ a dále lepší odhady $\binom{2m}{m}$. **[K 2.4-2.5]**, [[https://stream.cuni.cz/cs/Detail/5653|záznam]]|
| 6. 10. | Náhodné procházky. Úvod do vytvořujících funkcí. **[K 10.1-10.2]**, [[https://stream.cuni.cz/cs/Detail/5858|záznam]], slajdy [[https://kam.mff.cuni.cz/~fiala/KG1/011-vytvorujici_fce.pdf|doc. Fialy]] a [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace2.pdf|Martina Balka]].|
| 13. 10. | Vytvořující funkce: odvození vzorce pro Fibonacciho a Catalanova čísla. **[K 10.3-10.4]**, úvod do konečných projektivních rovin **[K 8.1]**, [[https://stream.cuni.cz/cs/Detail/6127|záznam]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace3.pdf| prezentace M. Balka]], [[https://kam.mff.cuni.cz/~fiala/KG1/020-Fanova_rovina.pdf|Fanova rovina (Fiala)]].|
| 20. 10. | Pokračování KPR: každá přímka má $n+1$ bodů a každým bodem prochází $n+1$ přímek a každá KPR má $n^2 + n + 1$ přímek i bodů; dualita; konstrukce KPR z algebraického tělesa **[K 8.1-8.2]**, [[https://stream.cuni.cz/cs/Detail/7319|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/025-konstrukce_z_teles.pdf|slajdy - konstrukce KPR z alg. tělesa (Fiala)]], |
| 27. 10. | Pokračování KPR: dokončení konstrukce KPR z algebraického tělesa **[K 8.2]** souvislosti navzájem ortogonálních latinských čtverců a KPR **[K 8.3]**, [[https://stream.cuni.cz/cs/Detail/7596|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/030-konstrukce_proj_roviny.pdf|slajdy - konstrukce KPR z NOLČ (Fiala)]]; [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace5.pdf| Slajdy KPR a NOLČ (Balko)]]|
| 3. 11. | Počítání dvěma způsoby. Spernerova věta o velikosti antiřetězce **[K 6.2]**, grafy bez $C_4$ mohou mít nanejvýš $O(n^{3/2})$ hran **[K 6.3]**,  Cayleyho formule pomocí POVYKOSů **[K 7.6]**. [[https://stream.cuni.cz/cs/Detail/7832|záznam]], Fialovy slajdy: [[https://kam.mff.cuni.cz/~fiala/KG1/040-Spernerova_veta.pdf|Spernerova věta]], [[https://kam.mff.cuni.cz/~fiala/KG1/035-kostry_rekurence.pdf|Rekurence na počet koster v grafu]], [[https://kam.mff.cuni.cz/~fiala/KG1/037-kostry_det.pdf|#koster přes determinanty]]|
| 10. 11. | Toky v sítích **[MV 2]**, Fialovy slajdy: [[https://kam.mff.cuni.cz/~fiala/KG1/070-toky.pdf|ukázka sítě]], [[https://kam.mff.cuni.cz/~fiala/KG1/065-Ford_Fulkerson.pdf|F-F algoritmus]], [[https://kam.mff.cuni.cz/~fiala/KG1/080-nekonecne_zlepsovani.pdf|cyklení F-F]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace6.pdf|Slajdy M. Balka]], [[https://stream.cuni.cz/cs/Detail/8026|záznam]]|
| 24. 11 | Aplikace toků:  Königova věta (v bipartitním grafu platí max párování = min vrcholové pokrytí), Hallova věta (nutná a postačující podmínka pro existenci systému různých reprezentantů neboli párování pokrývající jednu stranu bipartitního grafu), aplikace Hallovy věty (doplňování latinských obdélníků) -- dokončení příště. **[MV 4]**, **[M1]**, [[https://stream.cuni.cz/cs/Detail/8413|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/100-Hall.pdf|ukázka SRR]], [[https://kam.mff.cuni.cz/~fiala/KG1/110-latin.pdf|doplňování latinských obdélníků]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace7.pdf|slajdy M. Balka]]|
| 1. 12. | Míra souvislosti grafů **[MV 3]**, [[https://stream.cuni.cz/cs/Detail/9622|záznam]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace8.pdf|slajdy (Balko)]], [[https://kam.mff.cuni.cz/~fiala/KG1/060-konstrukce_cest.pdf|konstrukce $t$ cest (Fiala)]]|
| 8. 12. | Konstrukce $2$-souvislých grafů pomocí lepení uší **[K 3.8]**, Úvod do samoopravných kódů **[T]** [[https://stream.cuni.cz/cs/Detail/9752|záznam]], [[https://kam.mff.cuni.cz/~fiala/KG1/125-kody.pdf|slajdy (Fiala)]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace12.pdf|slajdy (Balko)]]|
| 15. 12. | Základní odhady na $A(n,d)$, lineární kódy **[T 3]**. [[https://stream.cuni.cz/cs/Detail/9916|záznam]] |
| 22. 12. | Dokončení samoopravných kódů: jak se dekóduje Hammingův kód a že je perfektní. **[T 3 + začátek 4]**; úvod do Ramseyovy teorie **[K 11 -- nové vydání]**, [[https://stream.cuni.cz/cs/Detail/10006|záznam]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace12.pdf|slajdy (Balko) - kódy]], [[https://kam.mff.cuni.cz/~balko/kgI1819/prezentace10.pdf|slajdy (Balko) - Ramsey]] |
| 5. 1. | Ramseyovy věty: více barev, $p$-tice, nekonečné grafy. **[M 2]**, [[https://stream.cuni.cz/cs/Detail/10079|záznam]]|


===== Zkouška =====

{{ :teaching:kg12021:okruhy_kg1.pdf |Popis formy a obsahu zkoušky.}}

{{page>teaching:bits:zdroje_kg1}}