Kombinatorika a grafy II

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

• 1. 10.: Edmondsův algoritmus na hledání největšího párování [T, VM]. Důkaz správnosti a analýza složitosti byly odsunuty do cvičení.
• 8. 10.: Tutteova věta o perfektním párování [VM, D], Petersenova věta o perf. párování v 3-regulárních 2-souvislých grafech [D].
• 15. 10.: Lemma o kontrahovatelné hraně pro vrcholově 3-souvislé grafy [D]. Pojem grafového minoru. Formulace Kuratowského a Wagnerovy věty s důkazem (část důkazu odsunuta do cvičení) [D].
• 22. 10.: Plochy, jejich konstrukce pomocí uší a křížítek. Zobecněný Eulerův vzorec, odhady na průměrný a minimální stupeň grafu nakresleného na dané ploše [Bo, Dv1].
• 29. 10.: Důkaz zobecněného Eulerova vzorce, Heawoodův vzorec pro horní odhad barevnosti grafů nakreslených na dané ploše [Dv1]. Brooksova věta [D, Dv2].
• 5. 11.: Vizingova věta [Dv2, D]. Perfektní grafy, slabá věta o perf. grafech [D].
• 19. 11.: Dilworthova věta jako důsledek slabé věty o perfektních grafech [DT]. Chordální grafy, jejich charakterizace pomocí perfektního eliminačního schématu (PES), konstrukce PES v polynomiálním čase, perfektnost chordálních grafů  [Ba, D,  HR].
  
• 26. 11.: Tutteův polynom, jeho definice pomocí sumy, ekvivalentní definice pomocí rekurencí, souvislost s počtem koster. Chromatický polynom: jeho definice pomocí Tutteova polynomu a jeho souvislost s počtem dobrých obarvení [Bo].
• 3 .12.: Formální mocninné řady a operace s nimi: existence inverzního prvku, skládání řad, derivace. Kombinatorické třídy a jejich obyčejné vytvořující funkce [W].
• 10. 12.: Exponenciální vytvořující funkce a "labelované" třídy [W]. Akce grupy na množině a související pojmy; lemma o orbitě a stabilizátoru (+na následujícím cvičení Burnsideovo lemma s důkazem) [Bo].
• 17. 12.: Příklad užití Burnsideova lemmatu na počítání tříd izomorfismu grafů na čtyřech vrcholech s daným počtem hran. Bondyho-Chvátalova věta o hamiltonovské kružnici a Diracova věta [D].
• 7. 1. Turánova věta [D], věta o počtu hran v grafu bez úplného minoru [D, v obecnější verzi pro grafy bez dělení úplného grafu], Erdős-Ko-Radoova věta [EKR].