Kombinatorika a grafy II NDMI012
Kdy a kde: v pondělí od 12:20 v S9.
Cvičení a cvičící: Cvičení vede Vít Jelínek. Zápočet ze cvičení je nutný pro absolvování zkoušky, podmínky získání zápočtu stanovuje cvičící.
Zkouška: Nebudou už vypsány žádné další termíny, ale pokud máte zájem přijít na zkoušku, kontaktujte mě a domluvíme se na termínu (ideálně se předdomluvte ve více lidech).
Zkouškové termíny jsou vypsány v SISu, upozorňuji, že ačkoli zápočet není podmínkou k přihlášení na zkoušku, je podmínkou k účasti na zkoušce. Zkouška má ústní formu, s možností písemné přípravy předcházející vlastnímu ústnímu zkoušení. Bude zkoušena znalost vět a definic z přednášky a jejich aplikace ( zkoušková témata).
Co bylo/bude na hodinách:
- 2.10.: Edmondsův kytičkový algoritmus pro nalezení největšího párování v grafu, části důkazu na cvičení. [VM]
- 9.10.: Perfektní párování: Tutteho věta o perfektním párování v obecném grafu. Petersenova věta, že 3-regulární graf bez mostu má perfektní párování. Gallai-Edmondsova věta (důkaz dokončen na cvičení). [VM,D]
- 16.10.: Existence kontrahovatelné hrany v 3-souvislém grafu. Tutteova charakterizace 3-souvislých grafů. Definice minoru. Kuratowského a Wagnerova věta pro rovinné grafy (část důkazu na cvičení). [VM,D]
- 23.10.: Kreslení grafů na plochy. Zobecněná Eulerova formule, průměrný stupeň grafu nakreslitelného na plochu. [Dv1]
- 30.10.: Vztah barevnosti a degenerovanosti grafu. Degenerovanost grafů nakreslitelných na plochy a Heawoodova formule. Brooksova věta. [Dv1,2]
- 6.11.: Hranová barevnost: souvislost s barevností linegrafu, Vizingova věta. [Dv2] Definice perfektních grafů, silná a slabá věta o perfektních grafech. [D]
- 13.11.: Důkaz slabé věty o perfektních grafech. Chordální grafy, perfektní eliminační schéma. Dilworthova věta na cvičení. [D]
- 20.11.: Tutteův polynom. Počet koster. Chromatický polynom. [B]
- 27.11.: Formální mocninné řady a operace s nimi - sčítání, násobení, převrácená hodnota, skládání, derivace. Obyčejné vytvořující funkce. Motivační příklad pro exponenciální vytvořující funkce. [W,FS]
- 4.12.: Exponenciální vytvořující funkce. [W,FS] Akce grupy na množině, stabilizátor, fixní body (definice).
- 11.12.: Akce grupy - stabilizátor, fixní body, orbita. Lemma o orbitě a stabilizátoru. Burnsideovo lemma (vážené). Příklady použití. [B,G]
- 18.12.: Turánova věta[D] a Erdős-Ko-Radoova věta[J]. (Přednášel Vít Jelínek.)
- 8.1.: Lemma o slunečnici.[J] Hamiltonovské grafy: Bondyho-Chvátalova věta a její důsledky, hamiltonovskost k-souvislého grafu s malou nezávislou množinou. [D]
Studijní materiály:
- Videozáznam z loňské přednášky (přednášel Vít Jelínek).
- [B] B. Bollobás: Modern graph theory, Springer, 1998.
- [D] R. Diestel: Graph theory.
- [W] Herbert S. Wilf: generatingfunctionology.
- [Dv1] Z. Dvořák: Prezentace o kreslení grafů na plochy.
- [Dv2] Z. Dvořák: Prezentace o Brooksově a Vizingově větě.
- [VM] T. Valla, J. Matoušek: Kombinatorika a grafy I
- [FS] P. Flajolet a R. Sedgewick: Analytic Combinatorics
- [G] T. Gowers: Group actions II: the orbit-stabilizer theorem
- [J] S. Jukna: Extremal combinatorics: with applications in computer science.(draft)