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
29. 3.	Zobecněná Eulerova formule, Heawoodova formule [Dv1, Dv2] záznam
12. 4.	Brooksova věta [Dv2] záznam
19. 4.	Vizingova věta [Dv2], perfektní grafy [D], záznam; Lemma o nafouknutí vrcholu je [D Lemma 5.5.4]

Užitečné zdroje KG2

Sbírka úloh
Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
[Sh] A. Shoemaker: Edmonds' Blossom Algorithm (notes)
[T] R. Tarjan Sketchy notes on [...] blossom algorithm for general matching
[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
[BCh] The Bondy and Chvátal Theorem
[D] R. Diestel: Graph Theory
[DT] Dilworth theorem: perfection of comparability graphs
[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
[EKR] The Erdős-Ko-Rado theorem
[HR] Y. Haimovitch, A. Raviv: Chordal graphs (ppt prezentace)
[W] H. Wilf: Generatingfunctionology
[R] G. Ringel: Map Color Theorem