Kombinatorika a grafy II (NDMI012)

Jan Hubička, hubicka@kam.mff.cuni.cz

• Přednáška: Po 10:40, S3
• Cvičení vede Jan Soukup.

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