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: