Zapocet: Na zkousku budete potrebovat zapocet (tyka se vsech forem studia).
Udeluje Vam ho cvicici, ve vetsine pripadu zapisuje prednasejici (u zkousky).
Pokud nepatrite
do zadneho kruhu (kombinovane studium apod.), podivejte se
sem.
Seznam prednasek a cviceni z DM
Emaily cvicicich:
Vit Jelinek: jelinek (zavinac) kam.mff.cuni.cz
Marek Krcal: marek.krcal (zavinac) seznam.cz
Diana Piguet: diana (zavinac) kam.mff.cuni.cz
Tomas Vanicek: vanicek (zavinac) fsv.cvut.cz
Zakladni literatura: J. Matousek a J. Nesetril, Kapitoly z diskretni matematiky, Karolinum 2000 (dotisky 2002, 2003; predchozi vydani lisici se jen v drobnostech: Matfyzpress 1996). K dostani v prodejne skript v Troji (240 Kc, Po-Pa 9-15) ci v Knihkupectvi Karolinum v Celetne 18 (loni 240 Kc, otevreno po-pa 9-19, so-ne 11-17), zacatkem semestru mozna maji nektere prodejny slevy. Nejake vytisky k vypujceni jsou snad tez v knihovne MFF. Kniha je napsana peclive, presto se Vam mohou hodit odhalene chyby.
1. prednaska 5.10. 3 motivacni problemy: satnarka (formulovano jako rozdavani darku na vanocni besidce), kresleni 1 tahem, propojovani 3+3 domku neprotinajicimi se vedenimi; (Kapitola 1.) ciselne obory (N={1,2,..}, Z, Q, R), suma, priklad dukazu matem. indukci, mnoziny, zapisy mnozin, rovnost dvou mnozin, prazdna mnozina, podmnozina, prunik, sjednoceni, rozdil, velikost mnoziny, potencni mnozina, velikost pot. mnoziny konecne mnoziny, usp. a neusp. dvojice, kart. soucin, relace (tj. binarni relace)
12.10. se prednaska kvuli imatrikulaci nekonala.
2. prednaska 19.10. vlastnosti relaci (reflexivita, symetrie, tranzitivita, ekvivalence), trida ekvivalence urcena prvkem x, jednoduchy priklad na ekvivalenci a tridy ekvivalence, rozklad mnoziny na tridy ekvivalence, (castecne) usporadani, linearni usporadani, jednoduche priklady na castecne a linearni usporadani, definice zobrazeni (=funkce), slozeni zobrazeni (je to skutecne zobrazeni), zobrazeni proste, na, bijekce, (Kapitola 2.) permutace, zapisy permutace
3. prednaska 26.10. 12:20 faktorial, pocet permutaci na n-prvkove mnozine je n!, pocty zobrazeni (resp. prostych zobrazeni, bijekci) z n-prvk. do k-prvk. mnoziny, kombinacni cislo - 2 definice (pomoci faktorialu, jako pocet k-prvk. podmn. n-prvk. mnoziny), dukaz jejich ekvivalence, zakladni vztahy mezi komb. cisly: (n nad k)=(n nad n-k), (n nad k)=(n-1 nad k-1)+(n-1 nad k), Pascaluv trojuhelnik, binomicka veta (ve tvaru (x+y) na n=...), jeji dukaz indukci podle n
4. prednaska 26.10. 14:00 multinomicka veta (bez dukazu), odhady faktorialu: n na (n/2) < n! < ((n+1)/2) na n, odhady komb. cisel: 2 na n / (n+1) < (n nad [n/2]) < 2 na n, princip inkluze a exkluze (PIE)
5. prednaska 2.11. vanocni besidka (satnarka), pocet zobrazeni z n-prvkove na l-prvkovou mnozinu (za pouziti PIE); (Kapitola 3.) uvod do teorie grafu: graf, kresleni grafu obrazkem, uplny graf, kruznice, cesta, (uplny) bipart. graf
6. prednaska 9.11. izomorfismus grafu, (indukovane) podgrafy, pocet induk. podgrafu grafu na n vrcholech je 2 na n, souvislost, komponenty grafu, vzdalenost v grafu, soused, matice sousednosti, stupen grafu, veta o sudosti (princip sudosti): soucet stupnu v lib. grafu je roven dvojnasobku poctu hran, dusledek: v kazdem grafu je pocet vrcholu licheho stupne sudy, definice skore grafu
7. prednaska 16.11. veta o skore, kresleni grafu 1 uzavrenym tahem: graf je eulerovsky (lze nakreslit 1 uzavrenym tahem) prave kdyz je souvisly a ma vsechny stupne sude, nektere jednoduche grafove operace (pridani a odebrani hrany, odebrani vrcholu, deleni hrany, deleni grafu), (vrcholove) 2-souvisly graf, hranove 2-souvisly graf
8. prednaska 23.11. 2-souv. graf zustane souvisly po vyhozeni hrany, deleni 2-souv. grafu je 2-souvisle, lemma o usich, graf je 2-souvisly <==> vznikne z trojuhelniku postupnym pridavanim a delenim hran, v 2-souvislem grafu kazde 2 vrcholy lezi na kruznici, v 2-souvislem grafu lezi kazde dve hrany na spolecne kruznici (bez dukazu), (Kapitola 4.) strom, list, strom s alespon 2 vrcholy ma alespon 2 listy, G je strom <==> G-list je strom, dusledek: G strom <==> z G dostaneme jednovrcholovy graf postupnym odebiranim listu, 4 charekteristiky stromu (Tvrzeni 4.1.4 skript) - dukaz priste
9. prednaska 30.11. 4 charekteristiky stromu (Tvrzeni 4.1.4 skript) - dukaz, kostra grafu, graf s ohodnocenymi hranami, minimalni kostra, Kruskaluv (hladovy) algoritmus na nalezeni min. kostry souv. grafu vcetne dukazu spravnosti (dokonceni dukazu priste)
10. prednaska 7.12. zopakovani a dokonceni dukazu spravnosti hladoveho (Kruskalova) algoritmu (poznamka: dukaz spravnosti udelan ponekud jinak nez ve skriptech; na zkousku staci znat kterykoliv z nich), Jarnikuv a Boruvkuv algoritmus (bez dukazu spravnosti), (Kapitola 5.) definice oblouku, rovinne grafy, rovinne nakresleni grafu, definice steny a topologicke kruznice, Jordanova veta o topologicke kruznici (bez dukazu), K_5 a K_3,3 nejsou rovinne grafy, G rovinny <==> kazde jeho deleni je rovinne, Kuratowskeho veta: G rovinny <==> G neobsahuje deleni K_5 ani deleni K_3,3 (implikace zleva doprava vyplyva z predchoziho, implikace zprava nedokazovana)
11. prednaska 21.12.
Euleruv vztah pro souvisle rovinne grafy,
horni odhad poctu hran v rovinnem grafu,
dusledek: kazdy rov. graf ma vrchol stupne nejvyse 5,
barveni grafu, barevnost nekterych grafu (kruznice,
uplny graf), veta o 5 barvach
Pro zajimavost: O problemu 4 barev je sepsana "popularizujici"
anglicky psana
kniha (o historii problemu, s jednoduse podanymi hlavnimi myslenkami reseni),
pred rokem byla
k dostani v Palaci knih Neoluxor
12. prednaska 4.1. barveni polit. map, problem 4 barev, vztah mezi barvenim rov. grafu a map, (Kapitola 6.) dukaz principu sudosti pocitanim 2 zpusoby, horni odhad na max. pocet hran grafu bez 4-cyklu, horni odhad na max. pocet hran grafu bez 3-cyklu, Spernerova veta o nezavislem systemu mnozin (dokonceni dukazu priste) (pozor, Spernerova veta je neco uplne jineho nez Spernerovo LEMMA, i kdyz oboji je ve skriptech blizko sebe, Spernerovo lemma jsme neprobirali)
13. prednaska 11.1. Spernerova veta o nezavislem systemu mnozin (dokonceni dukazu), (Kapitola 7.) Cayleyho formule o poctu koster uplneho grafu, tj. o poctu stromu na mnozine vrcholu {1,2,...,n} - mirne upraveny nejnovejsi (Pitmanuv) dukaz (na zkousku je pozadovano znat jeden (libov.) dukaz Cayleyho formule)