Diskrétní matematika

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

datum co se přednášelo [zdroj]
5. 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. [K 7.2]
12. 10.
19. 10.
26. 10.
2. 11.
16. 11. Úvod do teorie grafů: definice a základní značení, zoo grafů, bipartitnost, stupeň vrcholu, regulární graf, princip sudosti, isomorfismus grafů, odhad počtu neisomorfních grafů na n vrcholech. [K 4.1, 4.4 bez Věty o skóre]
23. 11. Grafy: 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, metrika v grafu. Stromy: definice, lemma o listu, princip indukce odtrháváním listů. [K 4.2, 5.1]
30. 11. Charakterizační věta pro stromy (5 ekvivalentních vlastností). Isomorfismus stromů: kódování pěstovaných stromů závorkami. [K 5.1, 5.2]
7. 12. Dokončení isomorfismu stromů: kódování zakořeněných stromů, převod obecných 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 5.2, 4.5, 4.6]
14. 12. Problém minimální kostry, Jarníkův a Borůvkův algoritmus. [K 5.3, 5.4]
21. 12. Cykly, cirkulace a řezy a jejich popis pomocí vektorových prostorů. [K 13.4, 13.5]
4. 1. Ramseyova věta pro grafy, dolní odhad Ramseyových čísel. [K 11.1–11.3]
11. 1. Cantorova-Bernsteinova věta a její grafový důkaz. Cayleyho formule pro počet koster úplného grafu, důkaz pomocí "povykosů". Zmínka o počítáni koster obecných grafů (rekurence s mazáním a kontrakcí hran, Kirchhoffova věta s determinantem bez důkazu). Desert na závěr semestru: Konstrukce de Bruijnových posloupností pomocí eulerovských tahů. [D; K 8.1, 8.5, 8.6, 4.6]

Literatura

Stránku spravuje Martin Mareš