teaching:kg22021_prednaska
Toto je starší verze dokumentu!
Přednáška z Kombinatoriky a grafů II 2020/21
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], záznam |
Užitečné zdroje KG2
- Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
- [Sh] A. Shoemaker: Edmonds' Blossom Algorithm (notes)
- [VM] T. Valla, J. Matoušek: Kombinatorika a grafy I
- [P] J. Plank: Edmonds' General Matching Algorithm Lecture Notes
- [Ba] P. Bartlett: Chordal graphs (zápisky z přednášky)
- [Bo] B. Bollobás: Modern Graph Theory
- [D] R. Diestel: Graph Theory
- [Dv1] Z. Dvořák: Prezentace o kreslení grafů na plochy, poznámky o kreslení na plochy
- [MT] B. Mohar, C. Thomassen: Graphs on Surfaces
- [Dv2] Z. Dvořák: Prezentace o Brooksově a Vizingově větě, poznámky
- [HR] Y. Haimovitch, A. Raviv: Chordal graphs (ppt prezentace)
- [W] H. Wilf: Generatingfunctionology
- [R] G. Ringel: Map Color Theorem
teaching/kg22021_prednaska.1616445451.txt.gz · Poslední úprava: 2021/03/22 21:37 autor: Martin Koutecky