Cvičení z Kombinatoriky a grafů 2

pondělí 14:00 v S7, LS 22/23

Ke své přednášce Kombinatorika a grafy 2 vedu cvičení, které bude probíhat nejspíše formou řešení příkladů v v náhodných skupinkách po 3-4 studentech.

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte před/během/po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi prosím emailem.

Co jsme dělali

13. 2.	Párování: opakování z KG1 a další příklady jako příprava na Edmondsův algoritmus (prošli jsme 1. až 3. příklad, 4. jsme udělali z části, 5. bude na přednášce, zbytek jsou zajimavé aplikace/zobecnění Hallovy věty)
20. 2.	Zaskočil Jan Soukup: příklady na kompletaci Edmondsova algoritmu a důkaz lemma o kontrakci květu (rozebráno až po 2c).
27. 2.	Perfektní párování: příklady na Tutteovu a Petersenovu větu (5. příklad na důkaz Tutteova-Bergeho vzorce jsme nedělali).
6. 3.	Minory a topologické minory: příklady (šestý příklad jsme nestihli), řešení lze najít třeba v poznámkách od Ireny Penev.
13. 3.	Třídy uzavřené na minory a kreslení grafů na plochy: příklady (tentokrát jsme prošli všechny).
20. 3.	Kreslení grafů na plochy a jejich barvení: příklady (prošli jsme všechny).
27. 3.	Barvení vrcholů a hlavně hran: příklady (pátý a šestý příklad jsme nedělali, ale jsou pěkné, neboť ukazují větu o hranovém barvení ekvivalentní větě o čtyřech barvách).
3. 4.	Perfektní grafy: příklady (poslední příklad jsme nestihli, bude nejspíš na přednášce).
10. 4.	Veselé Velikonoce
17. 4.	Chordální grafy a grafové polynomy: příklady (poslední příklad jsme nestihli, bude buď příště, nebo na přednášce).
24. 4.	Zaskočil Jan Soukup: příklady na vytvořující funkce, z nichž se stihly první dva a části a-d z třetího.
15. 5.	"Burnsideovo" lemma na počítání objektů až na symetrie: Příklady (čtvrtý jsme probrali jen stručně)
15. 5.	Začneme o 20 minut později. Příklady na extremální kombinatoriku.

Podmínky zápočtu

Zápočet bude za 2/3 bodů ze standardních úkolů (budou zadány i bonusové). Na každý úkol bude čas cca 13 dní, tj. do začátku cvičení za dva týdny. Body bude možné získat i za aktivní účast na cvičení. I poté je možné řešení odevzdat, jen dostanete max. polovinu bodů (ale zase vám mohu poskytnout nějakou nápovědu). Úkoly jsou zadávány a odevzdávají se přes Sovu; po prvním cvičení pošlu přístupový token – pokud se do SISu zapíšete později, dejte mi vědět. (pokud byste chtěli odevzdávat na papíře před cvičením, mohlo by to být také možné). Nebudete-li mít na konci semestru dostatek bodů, například kvůli dlouhodobé nemoci, dejte mi vědět.