Diskrétní matematika

V zimním semestru 2014/2015 přednášíme společně s prof. Nešetřilem Diskrétní matematiku pro matematiky [NMIN105]. Přednáška se koná každý čtvrtek od 9:00 v M1.

datum	co se přednášelo [zdroj]
2. 10.	Kombinatorické počítání: podmnožiny pomocí charakteristických funkcí, počet funkcí, počet relací. Druhy funkcí a druhy relací. [K 1.1–1.6, 3.1] Počet permutací a odhad faktoriálu. Kombinační čísla. [K 3.2–3.4] Princip inkluse a exkluse: problém šatnářky, latinské obdélníky a jejich počet. [K 3.6, 3.7] Částečně uspořádané množiny: minimální, maximální, nejmenší a největší prvky. Druhy uspořádání a příklad (např. lexikografické). Reprezentace částečných uspořádání pomocí inkluse. Existence minimálního prvku, lineární rozšíření. Axiom výběru a axiom dobrého uspořádání. Věta o dlouhém a širokém, věta o monotónní posloupnosti. [K 2.1–2.4] Princip počítání dvěma způsoby. Spernerova věta o nezávislých systémech množin. Aplikace na počet součtů v daném intervalu (střelba na terč). [K 7.2]
9. 10.
16. 10.
23. 10.
30. 10.
6. 11.
13. 11.
20. 11.	Úvod do teorie grafů: definice a základní značení, zoo grafů, bipartitnost, stupeň vrcholu, regulární graf, isomorfismus grafů, odhad počtu neisomorfních grafů na n vrcholech. [K 4.1]
27. 11.	Grafy: součet stupňů, princip sudosti, podgrafy a indukované podgrafy, grafové operace (přidání a odebrání vrcholu/hrany, dělení hrany), cesty a kružnice v grafech, souvislost a komponenty souvislosti. Stromy: definice, lemma o listu, princip indukce odtrháváním listů. [K 4.2, 4.4 bez Věty o skóre, 5.1]
4. 12.	Charakterizační věta pro stromy (5 ekvivalentních vlastností). Isomorfismus stromů: kódování zakořeněných a pěstovaných stromů závorkami. [K 5.1, 5.2]
11. 12.	Krátká odbočka ke vzdálenostem v grafech a metrice. Dokončení isomorfismu stromů: převod obecných stromů na zakořeněné pomocí centra. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Zmínka o analogické větě pro orientované grafy (nezkouší se). [K 4.2, 5.2, 4.5, 4.6]
18. 12.	Přednáška pro nemoc zrušena.
8. 1.	Ramseyova věta pro grafy, dolní odhad Ramseyových čísel. [K 11.1– 11.3]

Literatura

Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, Karolinum. Existuje několik různých vydání, která se liší číslováním kapitol; odkazy výše jsou podle nejnovějšího (oranžového). Také pozor na drobné chyby ve starších vydáních (viz errata). [K]
Sbírka úloh
Graham, Knuth, Patashnik: Concrete Mathematics (pokud máte chuť na něco pokročilejšího, toto je krásně napsaná knížka o věcech na pomezí diskrétní a spojité matematiky)
Lovász: Combinatorial Exercises (sbírka úloh, obvykle dosti šťavnatých)