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

Přednáším Kombinatoriku a grafy 2 ([[https://is.cuni.cz/studium/predmety/index.php?id=b470c244b68f466d232ed472e0c26a07&tid=&do=predmet&kod=NDMI012&skr=2020&fak=11320|NDMI012]]) každé pondělí v 15:40.

Pokud máte dotaz, který můžete vznést veřejně, nejlepší prostor je [[https://kam.mff.cuni.cz/owl/|OWL]]. Pokud vám nepřišel enrollment token, napište mi email. Pokud máte soukromý dotaz, napište mi email na adresu ''koutecky@iuuk.mff.cuni.cz'' a do předmětu uveďte text ''[KG2]''. 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] ^
| 1. 3. | Edmondsův algoritmus pro hledání největšího párování **[T, VM, Sh]** [[https://stream.cuni.cz/cs/Detail/11807|záznam]]. <fs smaller>Jak jít na ekvivalenci "($G$ má $M$-zlepšující cestu $\Leftrightarrow$ $G.C$ má $M.C$-zlepšující cestu"? **[VM]** na to jdou myslím zbytečně složitě; lepší je dokázat si pomocné tvrzení, že můžu přealternovat hrany na stonku a tím dostat kytku bez stonku a pak se případy rozeberou jednodušeji. To dělá **[T]**, ale ten mi přijde, že to zjednodušuje příliš. Asi nejvíc se mi líbí popis v **[Sh]**.</fs>|
| 8. 3. | Tutteova věta o perfektním párování **[VM]**, Petersenova věta ($2$-souvislý $3$-regulární graf má PP) **[D]**, [[https://stream.cuni.cz/cs/Detail/11953|záznam]]|
| 15. 3. | Tutteova charakterizace 3-souvislých grafů **[VM Lemma 7.2; D Thm 3.2.5]**, minory, Kuratowského věta **[VM kap. 7; D Chp 4]**, [[https://stream.cuni.cz/cs/Detail/12142|záznam]] |
| 22. 3. | Dokončení Kuratowského věty <fs smaller>($2$-souvislé grafy mají stěny ohraničeny kružnicemi: **[D Prop 4.2.6]**; graf má $K_5$ nebo $K_{3,3}$ jako minor právě když je má jako podrozdělení: **[D Lemma 4.4.2]**; $3$-souvislý případ Kuratowského věty je **[D Lemma 4.4.3]**; alternativně **[VM 7]**, ale není tam skoro vůbec rozebrané, proč když nenastanou 2 špatné případy už musí být všichni sousedé $y$ obsažení v segmentu mezi dvěma po sobě jdoucími sousedy $x$ na hranici relevantní stěny...)</fs>, úvod do grafů na plochách **[Dv1, MT 3, R 3-4]**, [[https://stream.cuni.cz/cs/Detail/12311|záznam]]|
| 29. 3. | Zobecněná Eulerova formule, Heawoodova formule **[Dv1, Dv2, R 4]** [[https://stream.cuni.cz/cs/Detail/12483|záznam]]|
| 12. 4. | Brooksova věta **[Dv2]** [[https://stream.cuni.cz/cs/Detail/12789|záznam]]|
| 19. 4. | Vizingova věta **[Dv2]** [[https://www.youtube.com/watch?v=OZWZpQmGp0g|animace Tomáše Slámy]], perfektní grafy **[D]** [[https://www.youtube.com/watch?v=Koc63QhxPgk|animace Tomáše Slámy]], [[https://stream.cuni.cz/cs/Detail/12967|záznam]], ; Lemma o nafouknutí vrcholu je **[D Lemma 5.5.4]**|
| 26. 4. | Chordální grafy **[Ba, D, HR]**, Bondy-Chvátalova věta **[BCh]**, **[[https://stream.cuni.cz/cs/Detail/13498|záznam]]**|
| 3. 5. | Tutteův polynom, jeho rekurentní vztahy pro mazání a kontrakce. Chromatický polynom, jeho vyjádření pomocí Tutteova polynomu **[Bo]**. [[https://stream.cuni.cz/cs/Detail/13608|záznam]] |
| 10. 5. | Úvod do formálních mocninných řad a obyčejných vytvořujících funkcí **[W]**, [[https://stream.cuni.cz/cs/Detail/13726|záznam]] <fs smaller>Bohužel záznam se přerušil před koncem -- chybí v něm ještě interpretace $1 + H(x) + H(x)^2 + ... = 1/(1-H(x))$ jakožto funkce, kde koeficient u $x^n$ určuje počet konečných posloupností hlavních jídel s cenou přesně n Kč. Zde se používá substituce $y=H(x)$ do výrazu $1/(1-x)$ a proto vyžadujeme, aby $[x^0]H(x) = 0$, tzn. aby neexistovalo žádné jídlo zdarma. To dává smysl, protože pokud je nějaké jídlo zdarma, tak např. posloupností za 0 Kč je nekonečně mnoho.</fs> |
| 17. 5. | Exponenciální vytvořující funkce **[W]**, akce grupy -- základní pojmy **[Bo]**, [[https://stream.cuni.cz/cs/Detail/13905|záznam]] |
| 24. 5. | Burnsiderovo lemma a jeho aplikace **[Bo]** [[https://stream.cuni.cz/cs/Detail/14032|záznam]]|
| 31. 5. | Extremální teorie grafů a hypergrafů -- Turánova věta **[D]**, grafy se zakázaným $K_r$ minorem mají lineárně mnoho hran **[D]**, Erdos-Ko-Rado věta. **[EKR]**, [[https://stream.cuni.cz/cs/Detail/14117|záznam]]|

{{ :teaching:kg22021:okruhy.pdf |Podoba zkoušky a okruhy}}


{{page>teaching:bits:zdroje_kg2}}