Kombinatorika a grafy II (NDMI012)

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

• Přednáška: Pá 10:40, S3
• Cvičení vede Josef Tkadlec.

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.

21. března

Nakrelsení grafů na plochy, zobecněná Eulerova formule, její důsledky pro degenerovanost a barevnost grafů nakreslitelných na danou plochu [Dv1]. Haywoodova formule.

25. března

Degenerované grafy, Brooksova věta [Dv2].

4. dubna

Vizingova věta o vztahu hranové barevnosti a největšího stupně [Dv2]. Pojem perfektního grafu..

11. dubna

Slabá věta o perfektních grafech [D]. 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].

25. 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]

2. května

Chromatický polynom. 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]. Video.

8. kvetna

Exponnenciální vytvořující funkce. Zoom Video.

Literatura