Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:kg22021_prednaska [2021/04/19 19:45] – přednáška 19. 4. Martin Koutecky
+++ teaching:kg22021_prednaska [2021/06/07 18:48] (aktuální) – zkouska Martin Koutecky
@@ Řádek 13: / Řádek 13: @@
 | 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]**, [[https://stream.cuni.cz/cs/Detail/12311|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]** [[https://stream.cuni.cz/cs/Detail/12483|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]**, perfektní grafy **[D]**, [[https://stream.cuni.cz/cs/Detail/12967|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}}