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. |
|
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
- 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]
- Martin Mareš: Kombinatorické drobnosti [D]
- 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)