Základy kombinatoriky a teorie grafů 2022/23 – 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 ve čtvrtek od 10.40 v K3. Cvičení vedeme společně s Majdou Mišinovou.

• Úč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-zavináč-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.
• Na předloňských a předpředloňských stránkách cvičení jsou videa s řešeními příkladů, letos budou příklady pravděpodobně podobné.

Co jsme dělali

Datum	Obsah
16. 2. 2023	Úvodní hodina. Příklady. Zadán nultý úkol.
23. 2. 2023	Toky v sítích. Příklady. Zadán první úkol.
23. 2. 2023	Souvislost grafů. Příklady.
9. 3. 2023	Hallova věta. Příklady. Deadline prvního DÚ.
16. 3. 2023	Rovinné grafy. Příklady. Zadán druhý úkol.
23. 3. 2023	Ramseyovky. Příklady.
30. 3. 2023	Ramseyovky podruhé. Příklady. Deadline druhého DÚ.
6. 4. 2023	Vytvořující funkce. Příklady.
13. 4. 2023	Hamiltonovské kružnice. Příklady.
20. 4. 2023	Povídání o Turingových strojích.
27. 4. 2023	P vs. NP. Příklady. Zadán třetí úkol.

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	#2.1	#2.2	#2.3	Součet
Pál Erdős	5	4	6	8	8	8	8	47
jardax	5							5
Anonymní ještěrka	5	4	6	8				23
Peet	5	4	6	8	8		8	39
Filip(1+i)	5	4	6	8	8	8	8	47
Žirafa	5	4	6	8				23
Pickle Rick	5	4	6	8				23
Yoda	5							5
Pecka	5	4	6	8				23
já	5	4	6	8				23
Věnceslav Horbař	5	4	6	8				23
přezdívka: Adam Zemánek	5	2	6	2	4			19
Okurka	5	4			6			15