Kombinatorika a grafy II

Přednáška v pondělí 12:20, S4

• 3. 10.: Charakterizace největšího párování pomocí volných střídavých cest. Lemma o tom, že kontrakce květu neovlivní existenci volné střídavé cesty. Edmondsův kytičkový algoritmus [T,VM].  Část důkazu správnosti přesunuta do cvičení.
• 10. 10.: Tutteova věta o perfektním párování [D,VM]. Petersenova věta o perfektním párování v 3-regulárním 2-souvislém grafu [D].
• 17. 10.: Lemma o kontrahovatelné hraně pro 3-souvislé grafy [D,VM], Tutteova charakterizace kontrahovatelných grafů [D]. Pojem grafového minoru, znění Kuratowského a Wagnerovy věty pro rovinné grafy (důkaz bude dokončen příště a na cvičení) [D,VM].
• 24. 10.: 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].
• 31. 10.: Nakreslení grafu na ploše, pojem buňkového nakreslení, zobecněná Eulerova formule, její důsledky pro počet hran grafu nakreslitelného na danou plochu, odhad na minimální stupeň takového grafu, Heawoodova formule [Dv1].
• 7. 11.: Brooksova věta o vztahu barevnosti a největšího stupně, Vizingova věta o vztahu hranové barevnosti a největšího stupně [Dv2].
• 14. 11.: Důkaz Vizingovy věty. Pojem perfektního grafu, slabá věta o perfektních grafech [D].
• 21. 11.: 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].
  
• 28. 11.: Tutteův polynom, jeho rekurentní vztahy pro mazání a kontrakce. Chromatický polynom, jeho vyjádření pomocí Tutteova polynomu [Bo].
• 5. 12.: 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].
• 12. 12.: Exponenciální vytvořující funkce [W]. Definice akce grupy na množině [Bo].
• 19. 12.: Další 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].
• 9. 1.: 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]