- 3. října
- Edmondsův algoritmus [VM]
Cvičení: dokončení důkazu Edmonsova algoritmu (kontrakce květu).
- 10. října
- Halova věta (opakování), 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]
Cvičení: každý k-regulrání (k-1)-souvislý graf má perfektní párování. Hallova veta z Tutteovy.
- 17. října
- 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í, částečně na příští přednášce) [VM, D].
Cvičení: každý 3-regulrání graf s max. dvěma mosty má perfektí párování. Minor K3,3 implikuje dělení K3,3. Minor K5 implikuje dělení K5 nebo dělení K3,3.
- 24. října
- 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].
Cvičení: Graf je vnějškově rovinný pokud neobsahuje minor K4 nebo K2,3. Kombinatorická jednoznačnost nakreslení.
- 31. října
- Nakrelsení grafů na plochy, zobecněná Eulerova formule, její důsledky pro degenerovanost a barevnost grafů nakreslitelných na danou plochu [Dv1].
Cvičení: Každý 3. souvsilý rovinný graf ma kombinatoricky jednoznačné nakreslení, klasifikace ploch, dokončení důkazu Eulerovy formule pro mosty.
- 7. listopadu
- Haywoodova formule, degenerované grafy, Brooksova věta [Dv2].
Cvičení: Výuka kreslení na projektivní roviny (K5, K6), torus (K7) a Kleinovu láhev (zde nakreslit K7 nejde). Duály grafů. Hladový algoritmus na bipartitním grafu může použít libovoně mnoho barev.
- 14. listopadu
- 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].
Cvičení: Hladový algoritmus na bipartitním grafu.
- 21. listopadu
- Přednáší Vít Jelínek. 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]. Bondyho-Chvátalova věta o hamiltonovskosti [BCh].
Cvíčení v týdnu 19-23. listopadu odpadá.
- 28. listopadu
- Počítání koster, chromatický polynom, spolehlivost grafu. Tutteův polynom - Nullity-rank expanze a multiplikativita pro disjunkntní sjednocení. [Bo]
Cvičení: Příklady a vlastnosti perfektních grafů, chordální grafy
-
- 5.prosince
- Tutteův polynom, jeho rekurentní vztahy pro mazání a kontrakce. Univerzální polynom a recipte theorem. Chromatický polynom, jeho vyjádření pomocí univerzálního polynomu [Bo]
- 12.prosince
- 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. Exponenciální vytvořující funkce (motivace)[W].
- 19.prosince
- Exponnenciílní vytvořující funkce. 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].
- 14.prosince.
- 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]