Cvičení z Kombinatoriky a Grafů 2 - Pondělí 15:40, Středa 17:20
Cvičení probíhá prezenční formou ve pondělí 15:40 a středu 17:20. Na začátku semestru budou středeční a pondělní cvičení ekvivalentní, tak si můžete vybrat na které přijít.
Případné rozdíly kdyžtak explicitně zmíním. Jedná se o cvičení k přednášce Honzy Hubičky.
Dotazy k cvičení, či obecně ke kombinatorice prosím směřujte na email soukup@kam.mff.cuni.cz.
Materiály
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 budete mít dva týdny,
po prvním týdnu se pokusím úlohy opravit a do deadlinu je můžete odevzdat opravené.
Body bude možné získat i za aktivní účast na cvičení.
I po deadlinu je možné řešení odevzdat, jen dostanete max. polovinu zbytku bodů.
Ú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, je to také možné).
Nebudete-li mít na konci semestru dostatek bodů z rozumného důvodu, například kvůli dlouhodobé nemoci, dejte mi vědět, nějak to vyřešíme.
Instrukce k odevzdávání úloh
Všechna tvrzení ve svých řešeních řádně zdůvodněte, a to i když v zadání není slovo "dokažte".
Můžete samozřejmě již bez důkazu používat tvrzení a věty dokázané na přednášce nebo na cvičení.
Nebojte se odevzdat i jen částečná řešení.
Náplň cvičení
1. hodina (19-21. 2. 2024)
- Edmondsnův kytičkový algoritmus
Úlohy ze cvičení
Domácí úkol (odevzdat do 4.-6.3. před příslušným cvičením)
2. hodina (26, 28. 2. 2024)
- Perfektní párování, Tutteova věta
Úlohy ze cvičení
Domácí úkol (odevzdat do 11.-13.3. před příslušným cvičením)
3. hodina (4-6. 3. 2024)
Úlohy ze cvičení
Domácí úkol (odevzdat do 18-20.3. před příslušným cvičením)
4. hodina (11-13. 3. 2024)
Příklady na procvičení minorů
5. hodina (18-20. 3. 2024)
Úlohy ze cvičení
Domácí úkol (odevzdat do 3-8.4. před příslušným cvičením)
6. hodina (25. 3. 2024)
Úlohy ze cvičení
Domácí úkol (odevzdat do 10-15.4. před příslušným cvičením)
7. hodina (3-8. 4. 2024)
- Barvení grafů, Perfektní grafy
Úlohy ze cvičení (3.4.)
Úlohy ze cvičení (8.4.)
8. hodina (10-15. 4. 2024)
- Perfektní grafy, Chordální grafy
Úlohy ze cvičení (10.4.)
Úlohy ze cvičení (15.4.)
Domácí úkol (odevzdat do 24.-29.4. před příslušným cvičením)
9. hodina (17-22. 4. 2024)
- Chordální grafy, Tutteův polynom
Úlohy ze cvičení (17.4.)
Úlohy ze cvičení (22.4.)
Domácí úkol (odevzdat do 1.-6.5. před příslušným cvičením)
10. hodina (24. 4. 2024)
Úlohy ze cvičení (24.4.)
Úlohy ze cvičení (29.4.)
Domácí úkol (odevzdat do 8.-13.5. před příslušným cvičením)
11. hodina (6. 5. 2024)
- Exponenciální vytvořující funkce
Úlohy ze cvičení
Domácí úkol (odevzdat do 20.-29.5. před příslušným cvičením)
12. hodina (13-15. 5. 2024)
Úlohy ze cvičení (13.5.)
Úlohy ze cvičení (15.5.)
Domácí úkol (odevzdat do 27.-29.5. před normálním časem cvičení)
13. hodina (20-22. 5. 2024)
- Exponenciální vytvořující funkce a Extremální kombinatorika
Úlohy ze cvičení (20.5.)
Úlohy ze cvičení (22.5.)