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).

• Účast je (samozřejmě) nepovinná.
• Budou nějaké úkoly za nějaké body (celkem alespoň 80) a na zápočet budete muset trochu projevit zájem (20 bodů).
• Úlohy prosím odevzdávejte mailem na matej-at-kam.mff.cuni.cz (ideálně samozřejmě v LaTeXu). Pokud o LaTeXu moc nevíte, na stránkách PraSete je návod, jak ho nainstalovat a i nějaké základy. Odtud si můžete stáhnout ukázkovou templatu na domácí úkoly. Kdyby něco, pište.
• Úlohy můžete odevzdávat kdykoliv, ale každá série bude mít nějaký deadline, před ním budete dostávat dvojnásobek bodů.
• Matoušek, Valla: Kombinatorika a grafy I.

Co jsme dělali

Datum	Obsah
18. 2. 2020	Úvodní hodina, grafy atp. Příklady. Zadán nultý úkol.
25. 2. 2020	Toky v sítích atp. Příklady. Zadán první úkol.
3. 3. 2020	Toky v sítích, souvislost grafů. Příklady.
10. 3. 2020	Souvislost grafů. Příklady.
17. 3. 2020	První 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. 2020	Druhé 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. 2020	Další 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. 2020	Ramseyovky. 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. 2020	Ramseyovky podruhé. Příklady (stejné jako minule). Řešení: 1, 2, 3, 4, 5, 6.
21. 4. 2020	Vytvoř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. 2020	Vytvoř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. 2020	P vs. NP I. Příklady. Řešení: 1, 8 (ostatní úlohy viz hinty).
12. 5. 2020	P vs. NP II. Příklady. Řešení: 1, 2, 3, 4.
19. 5. 2020	Hamiltonovské 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