Kombinatorika a grafy II (NDMI012)
Konzultace po dohodě emailem. Do subjektu emailů pište "KG2".
Odpřednesená látka
- 21. února
- Edmondsův algoritmus [VM].
Youtube video Tomáše Slámy
28. února
Tutteova věta o existenci perfektního párování, Petersenova věta o perfektním párování v 2-souvislém a 3-regulráním grafu [VM]
7. března
Lemma o kontrahovatelné hraně pro 3-souvislé grafy [VM,D], Tutteova charakterizace 3-souvislých grafů [D]. Definice minoru.
14. března
Kuratowského-Wagnerova věta (důkaz bude dokončen částečně na cvičení) [VM, D]. "Definice" plochy. Homeomorfismus. Přidání ucha. Na konci bylo přidání křižítka, které zopakuji. Cross-cap (křižítko)? na youtube.
Literatura
Záznamy přednášek Víta Jelínka
Zápisky Tomáše Slámy
[Ba] P. Bartlett: Chordal
graphs (pdf zápisky z přednášky)
[BCh] The Bondy
and Chvátal theorem
[Bo] B. Bollobás: Modern Graph Theory
[D] R. Diestel: Graph Theory
[Dv1] Z. Dvořák: Prezentace
o kreslení grafů na plochy (pozor, používá se tam jiná definice
rodu plochy než na přednášce)
[Dv2] Z. Dvořák: Prezentace
o Brooksově a Vizingově větě
[EKR] The
Erdős-Ko-Rado theorem
[HR] Y. Haimovitch, A. Raviv: Chordal
graphs (ppt prezentace)
[T] R. Tarjan: Sketchy
notes on [...] blossom algorithm for general matching
[VM] T. Valla, J. Matoušek: Kombinatorika a grafy I
[W] H. Wilf: Generatingfunctionology