Přednáším Kombinatoriku a grafy 2 (NDMI012) každé pondělí v 15:40.
Pokud máte dotaz, který můžete vznést veřejně, nejlepší prostor je 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.
| datum | co se přednášelo [zdroj] |
|---|---|
| 1. 3. | Edmondsův algoritmus pro hledání největšího párování [T, VM, Sh] záznam. 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]. |
| 8. 3. | Tutteova věta o perfektním párování [VM], Petersenova věta ($2$-souvislý $3$-regulární graf má PP) [D], 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], záznam |
| 22. 3. | Dokončení Kuratowského věty ($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…), úvod do grafů na plochách [Dv1, MT 3, R 3-4], záznam |
| 29. 3. | Zobecněná Eulerova formule, Heawoodova formule [Dv1, Dv2, R 4] záznam |
| 12. 4. | Brooksova věta [Dv2] záznam |
| 19. 4. | Vizingova věta [Dv2] animace Tomáše Slámy, perfektní grafy [D] animace Tomáše Slámy, 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], 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]. záznam |
| 10. 5. | Úvod do formálních mocninných řad a obyčejných vytvořujících funkcí [W], záznam 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. |
| 17. 5. | Exponenciální vytvořující funkce [W], akce grupy – základní pojmy [Bo], záznam |
| 24. 5. | Burnsiderovo lemma a jeho aplikace [Bo] 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], záznam |