Základy kombinatoriky a teorie grafů 2019/20 – cvičení

Cvičení pro přednášku Základy kombinatoriky a teorie grafů [NMIN331] (vyučující Jan Kratochvíl a Pavel Valtr). Scházíme se v úterý od 12.20 v K2 (tj. po přednášce).

Co jsme dělali

DatumObsah
18. 2. 2020Úvodní hodina, grafy atp. Příklady. Zadán nultý úkol.
25. 2. 2020Toky v sítích atp. Příklady. Zadán první úkol.
3. 3. 2020Toky v sítích, souvislost grafů. Příklady.
10. 3. 2020Souvislost grafů. Příklady.
17. 3. 2020První virtuální cvičení. Místo přednášky si dočtěte kapitolu 3 a přečtěte kapitolu 4 (bez 4.1) ve skriptech. Jako cvičení si spočítejte příklady. Na poslední stránce jsou hinty (nejdřív si to zkuste rozmyslet bez nich!). Experimentálně vyrobená řešení: 1, 2a, 2b, 3, 4, 5, BONUS.
24. 3. 2020Druhé virtuální cvičení. Přednášku vám zadal přednášející, já vyrobil stručné opakování. Jako cvičení si spočítejte příklady. Na druhé stránce jsou hinty (nejdřív si to zkuste rozmyslet bez nich!). Řešení (warning: disturbing content): 1, 2, 3, 4, 5, 6, 7.
31. 3. 2020Další barevnost. Příklady. Na druhé stránce jsou hinty (nejdřív si to zkuste rozmyslet bez nich!). Řešení: 1, 2, 3, 4, 5.
7. 4. 2020Ramseyovky. Příklady. Na druhé stránce jsou hinty (nejdřív si to zkuste rozmyslet bez nich!). Povídání o Ramseyovkách: Nekonečné varianty, kompaktnost, konkrétní příklad na Gödelovu větu. Bylo to vyráběné na několik etap, takže tam můžou být nekonzistence a některé věci asi opakuju vícekrát. Není povinné se koukat.
14. 4. 2020Ramseyovky podruhé. Příklady (stejné jako minule). Řešení: 1, 2, 3, 4, 5, 6.
21. 4. 2020Vytvořující funkce. Příklady. Třetí série DÚ. Řešení: 2, 3, 4, 5, 6, výpočet rekurence u 6.
28. 4. 2020Vytvořující funkce II. Příklady (z minula). Povídání o rychlé Fourierově transformaci (občas omylem říkám "kořeny" místo "koeficienty").
5. 5. 2020P vs. NP I. Příklady. Řešení: 1, 8 (ostatní úlohy viz hinty).
12. 5. 2020P vs. NP II. Příklady. Řešení: 1, 2, 3, 4.
19. 5. 2020Hamiltonovské kružnice. Příklady. Řešení: 1, 2, 3, 4.

Výsledky

Pokud tady chcete vidět i svoje výsledky, pošlete mi s tím souhlas a nějakou přezdívku :).
Přezdívka #0 #1.1 #1.2 #1.3 #1.4 #2.1 #2.2 #2.3 #3.1 #3.2 #3.3 #3.4 #3.5 Součet
Pál Erdős 5 4 4 6 8 6 8 8 6 4 6 4 12 81
Konicek23 5 4 4 6 6 4 12 41
8008 5 4 4 6 4 23
fifa000001 5 4 4 6 2 21
Georginho 5 4 4 6 6 8 6 4 4 47
KITA 5 4 4 6 8 27
furu 5 4 4 6 6 2 27
Surat 5 4 4 6 2 21
Fialová ovečka 5 4 4 6 6 8 8 6 4 6 4 12 73
Tesserekt 5 4 4 6 6 8 33
rátok 5 4 9
Zvíře 5 4 6 8 23
pampeliška 5 5
PivoT 5 4 4 6 4 23
yellowinastrip 5 4 6 8 23
Vingi 5 4 4 6 4 23
Uaaaa 5 4 4 6 4 23
CM 5 4 4 13
Královna 5 4 6 8 23
8547 5 2 8 8 23