Kombinatorika a grafy II (NDMI012)
Konzultace po dohodě emailem. Do subjektu emailů pište "KG2".
Odpřednesená látka
- 19. unora
- Edmondsův algoritmus [VM].
Youtube video Tomáše Slámy
- 26. unora
- 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]
- 4. brezna
- Lemma o kontrahovatelné hraně pro 3-souvislé grafy [VM,D], Tutteova charakterizace 3-souvislých grafů [D]. Definice minoru. Kuratowského-Wagnerova věta (důkaz bude dokončen částečně na cvičení) [VM, D].
- 11. brezna
- Nakrelsení grafů na plochy, zobecněná Eulerova formule, její důsledky pro degenerovanost a barevnost grafů nakreslitelných na danou plochu [Dv1].
- 18. brezna
- Poslední část důkazu Kuratowského a Wagnerovy věty. Základní pojmy týkající se ploch: homeomorfismus, přidání ucha a křížítka, klasifikace ploch, rod plochy [Dv1].
- 25. brezna
- Haywoodova formule, degenerované grafy, Brooksova věta [Dv2].
- 8. dubna
- Vizingova věta o vztahu hranové barevnosti a největšího stupně [Dv2]. Pojem perfektního grafu, slabá věta o perfektních grafech [D].
- 15. dubna
- Chordální grafy, existence perfektních eliminačních schémat pro ně, jejich perfektnost, jejich rozpoznávání v polynomiálním čase [Ba, D, HR].
- 22. dubna
- Bondyho-Chvátalova věta o hamiltonovskosti [BCh]. Počítání koster, chromatický polynom, spolehlivost grafu. Tutteův polynom - Nullity-rank expanze a multiplikativita pro disjunkntní sjednocení. [Bo]
- 29. dubna
- Formální mocninné řady a základní operace s nimi: sčítání, násobení, existence převrácené hodnoty, skládání, derivace [W]. Obyčejné vytvořující funkce.[W].
- 6. kvetna
- Exponnenciílní vytvořující funkce.
- 13. kvetna
- Definice akce grupy na množině a pojmy související s akcemi grup: množina pevných bodů, stabilizátor, orbita. Lemma o orbitě a stabilizátoru, "Burnsideovo" lemma (i ve verzi s orbitami rozdílných vah) a příklady jeho použití [Bo].[W].
- 20. kvetna
- Plán: Turánova věta [D], lineární odhad na počet hran v grafu bez zakázaného úplného minoru [D], Erdős-Ko-Radoova věta [EKR]
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