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

Stránku spravuje Martin Mareš