Kombinatorika a grafy II

Přednáška ve středu 15:40, S3

Co se probíralo:

• 2. 10.: Tutteova věta o perfektním párování, Petersenova věta o perfektním párování v 3-regulárních 2-souvislých grafech [D].
• 9. 10.: Lemma o kontrahovatelné hraně, Tutteova charakterizace 3-souvislých grafů, pojem grafového minoru, Kuratowského a Wagnerova věta [D].
• 16. 10.: Dokončení důkazu Kuratowského a Wagnerovy věty [D]. Začátek topologie ploch: pojem homeomorfismu [Dv1]
• 23. 10.: Plochy a jejich konstrukce pomocí přidávání uší a křížítek, klasifikace ploch, nakreslení grafu na plochu, buňkové nakreslení, zobecněná Eulerova formule a její důsledek pro průměrný stupeň grafu nakresleného na dané ploše [Dv1].
• 30. 10.: Důkaz zobecněné Eulerovy formule, odhad na minimální stupeň a degenerovanost grafu nakresleného na danou plochu, Heawoodův odhad na barevnost grafu nakresleného na plochu [Dv1].
• 6. 11.: Brooksova a Vizingova věta [Dv2].
• 13. 11.: Perfektní grafy, důkaz slabé věty o perfektních grafech, Dilworthova věta jako její důsledek (dokázána na cvičení) [D].
• 20. 11.: Chordální grafy, jejich charakterizace pomocí perfektních eliminačních schémat, jejich perfektnost, algoritmy pro nalezení jejich maximální kliky a optimálního obarvení [Ba,HR].
• 27. 11.: Tutteův polynom, jeho ekvivalentní charakterizace pomocí rekurencí přes kontrakce a mazání hran, souvislost s chromatickým polynomem [Bo].
• 4. 12.: Formální movninné řady, operace s nimi, existence multiplikativní inverze (jen pro řady jedné proměnné nad reálnými čísly), obyčejné vytvořující funkce tříd kombinatorických objektů (včetně vytvořujících funkcí více proměnných, probíraných na cvičení) [W].
• 11. 12.: Exponenciální vytvořující funkce a příklady jejich používážití [W]. Úvod do grupových akcí, lemma o orbitě a stabilizátoru [Bo].
• 18. 12.: Burnsideovo lemma, včetně vážené verze, příklady jeho použítí [Bo].
• 8. 1.: Turánova věta [D], Bondy-Chvátalova věta [BCh], Erdős-Ko-Radoova věta [EKR].

Literatura: