Kombinatorika a grafy II

Přednáška v pátek 12:20, S9

• 9. 10.: Edmondsův kytičkový algoritmus [T, VM]. Důkaz správnosti byl z větší části odsunut do cvičení.
• 16. 10.: Tutteova věta o perfektním párování [VM,D], Petersenova věta o tom, že 3-regulární 2-souvislé grafy mají perfektní párování [D].
• 23. 10.: 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í, částečně na příští přednášce) [VM, D].
• 30. 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].
• 6. 11.: Nakrelsení grafů na plochy, zobecněná Eulerova formule, její důsledky pro degenerovanost a barevnost grafů nakreslitelných na danou plochu [Dv1].
• 13. 11.: Brooksova věta a Vizingova věta [Dv2].
• 20. 11.: Perfektní grafy: slabá věta o perfektních grafech [D] (+na následujícím cvičení Dilworthova věta [DT]).
• 27. 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].
• 4. 12.: Tutteův polynom, jeho rekurentní vztahy pro mazání a kontrakce. Chromatický polynom, jeho vyjádření pomocí Tutteova polynomu [Bo].
• 11. 12.: Formální mocninné řady a operace s nimi: existence převrácené hodnoty a složení mocninných řad, derivace. Obyčejné vytvořující funkce, kombinatorický význam jejich sčítání a násobení [W].
• 18. 12.: Exponenciální vytvořující funkce a kombinatorický význam jejich sčítání a násobení [W]. Akce grupy na množině - základní pojmy [Bo].
• 8. 1.: Lemma o orbitě a stabilizátoru, "Burnsideovo" lemma (i ve verzi s orbitami rozdílných vah)  a příklady jeho použití [Bo].
• 15. 1.: Turánova věta [D]. Lineární odhad na počet hran grafu se zakázaných úplným minorem [D]. Erdős-Ko-Radoova věta [EKR].