Odkaz na bilou karolinku toho (zatim), jak vidite, mnoho neobsahuje. Zakladni literatura:

J. Matousek a J. Nesetril, Kapitoly z Diskretni matematiky, MATFYZPRESS 1996.

K zakoupeni v prodejne ERUDIO v budove MFF na Malostranskem namesti. K pujceni v knihovne v budove v Karline. Prednaska se kona v poslucharne M1 na Karlove v utery od 15:40 do 17:10. Planuju probrat prinejmensim kapitoly 1 (Zakladni znaceni), 2 (Kombinatoricke pocitani),  3 (Grafy: uvod), 4 (Stromy), 5 (Rovinne kresleni grafu), 6 (Pocitani dvema zpusoby) a 7 (Pocet koster); plus neco ze zaverecnych ctyrech kapitol. Zde je prehled dosud probrane latky.

1. prednaska 28.9.1999: Motivacni problem stridavych matic; K1. ciselne obory (N, Z, Q, R a C), cele casti, suma, soucin; mnoziny: zapisy, mohutnost, potence, prazdna mn., sjednoceni, prunik, rozdil, podmnozina, disjunktni mnoziny,  de Morganovy vzorce; matematicka indukce, priklad dukazu matem. indukci (n!>2^n pro kazde n>=4); relace: neusp. a usp. dvojice, kartezsky soucin, relace mezi X a Y, relace na X, znazorneni relace sipkami, ekvivalence, tridy ekvivalence.

2. prednaska 5.10.1999: Dalsi typy  relaci: funkce (zobrazeni), prosta f., f. na, bijekce, skladani funkci; usporadani, linearni u., ostre u., znazornovani u. Hasseho diagramem. K2. Pocet funkci z n-prvkove mnoziny do m-prvkove je m^n, je to vlastne pocet slov delky n nad m-prvkovou abecedou, Pocet podmnozin n-prvkove mnoziny je 2^n; permutace mnoziny X, zapisy permutaci, sipkovy graf p. se sklada z disj. cyklu, Pocet p. n-prvkove mnoziny je n!; binomicky koeficient B(n, k), Pocet k-prvkovych podmnozin n-prvkove je B(n, k) (dukaz priste).

3. prednaska 12.10.1999: Dukaz dluzeny z minula, vlastnosti binom. koeficientu: B(n, k)=B(n, n-k), B(n, k)=B(n-1, k)+B(n-1, k-1) a mnoz. vyklad techto vztahu, binom. veta: (1+x)^n=..., multinomicke koeficienty a multinom. veta (bez dukazu); odhad faktorialu: e.(n/e)^n <= n! <= e.n.(n/e)^n (indukci pouze horni odhad, jako ve skriptech, z nerovnosti 1+x<= e^x), uvedena Stirlingova formule, znaceni f(n)=O(g(n)), dalsi asympt. znaceni jen zmineno; PIE i s dukazem (timto: kazdy prvek sjednoceni prispiva 1 vlevo i vpravo), popularni formulace problemu satnarky.

4. prednaska 19.10.1999: Veta o satnarce, vzorec pro Eulerovu funkci fi (bez dukazu) K3. Zakladni pojmy teorie grafu, uplny graf, kruznice, cesta, u. bip. graf, isomorfismus grafu, podgraf, indukovany podgraf, souvislost, komponenty, vzdalenost v grafu, ma vlastnosti metriky (bez dukazu), matice sousednosti, stupen vrcholu, skore grafu, Princip sudosti (soucet stupnu=2|E|), pocet lichych vrcholu je sudy.

5. prednaska 26.10.1999: Havlova-Hakimiho veta o skore (posloupnost cisel je skore prave kdyz jista jina posloupnost je skore), kresleni grafu jednim tahem, pojem tahu a uzavreneho eulerovskeho tahu, eulerovsky graf, veta o eulerovskych grafech (graf je eulerovsky prave kdyz je souvisly a ma vsechny stupne sude, trochu neplati kvuli izolovanym vrcholum), pojem orientovaneho grafu, kresleni or. grafu jednim tahem, veta o or. eulerovskych grafech ("dukaz je obdobny," t.j. bez dukazu).
 
6. prednaska 2.11.1999:  Definice (vrcholove) 2-souvisleho grafu, grafove operace vyhozeni vrcholu, vyhozeni (pridani) hrany, deleni hrany, jak se chovaji ke 2-souvislosti, usate lemma (graf je 2-souvisly, prave kdyz se da vytvorit  z kruznice pridavanim usi), kazde 2 vrcholy ve 2-souv. grafu lezi na kruznici (dukaz pomoci usateho lemmatu). K4. Definice stromu, lema o existenci koncovych vrcholu, 5 ekvivalentnich definic stromu (dokazal jsem skoro vse, krome ekvivalence strom <-> je souvisly a |V|=|E|+1).

7. prednaska 9.11.1999: Dukaz dluzeny z minula, algoritmus pro rozhodovani izomorfismu stromu (korenove stromy, korenovy izomorfismus, alg. pro nej pomoci 0-1 kodu, excentricita vrcholu, centrum grafu a stromu, prevod obecnych stromu na korenove), kostra souvisleho grafu, kostra existuje, problem minimalni kostry, Kruskaluv hladovy algoritmus pro hledani min. kostry (zatim bez dukazu).

8. prednaska 16.11.1999: Dukaz spravnosti Kruskalova algoritmu, problem (vazene) nejkratsi cesty v grafu, Dijkstruv algoritmus, dukaz spravnosti Dijkstrova algoritmu. K5. Definice rovinneho oblouku, rovinne nakresleni grafu, rovinne grafy.

9. prednaska 23.11.1999: Steny nakresleni, definice topologicke souvislosti a obloukove souvislosti (v rovine), kresleni grafu na sfere, stereograficka projekce, graf je roviny <-> ma rovinne nakresleni lomenymi carami (bez dukazu),  topologicka kruznice, Jordanova veta (bez dukazu -:) ), K_5 neni rovinny a ani K_{3,3} neni rovinny, v kazdem nakresleni 2-souv. rov. grafu ma kazda stena za hranici kruznici (bez dukazu), Kuratowskiho veta (bez dukazu -:) ), Eulerova formule (pro souv. rov. graf plati: |V|-|E|+s=2), definice platonskeho telesa, Veta: existuje prave 5 platonskych teles (tetraedr, hexaedr, oktaedr, dodekaedr, ikosaedr) - dukaz priste.

10. prednaska 30.11.1999: Dukaz vety o platonskych telesech, rovinny graf s n vrcholy ma nejvyse 3n-6 hran, rovinny graf bez trojuhelniku
ma nejvyse 2n-4 hran, K_5 a K_{3,3} nejsou rovinne, rov. graf ma vzdy vrchol stupne nejvyse 5, barveni grafu, barevnost grafu, problem 4 barev, veta o 5 barvach (dukaz pomoci kontrakci hran).

11. prednaska 7.12.1999: K6. Spernerovo topologicke lemma (v kazdem vrcholovem obarveni-ne nutne radnem-skorotriangulace barvami 1, 2, a 3, pricemz je splnena jista podminka pro barvy na obvodu, se nutne vyskytuje trojuhelnikova stena s vrcholy obarvenymi vsemi tremi barvami). Aplikace: Brouwerova veta o pevnem bodu (bez dukazu) a hra (pseudo)HEX (s dukazem i hranim). Spernerovo mnozinove lemma (kazdy antiretezec v castecnem usporadani potence {1, 2, ..., n} inkluzi ma <= B(n, [n/2]) clenu). Pul dukazu, druha pulka za tyden.

12. prednaska 14.12.1999: Dokonceni dukazu Spernerova mnozinoveho lemmatu. Cauchy-Schwarzova nerovnost, dukaz,  a jeji pouziti v dukazu odhadu |E|<(n^{3/2}+n)/2 pro pocet hran grafu, ktery ma n vrcholu a nema podgraf K_{2,2}. K7. Cayleyho veta (K_n ma n^{n-2} koster) a zacatek jejiho dukazu bijekci pomoci obratlovcu.

13. prednaska 4.1.2000: Dokonceni prvniho dukazu Cayleyovy vety (bijektivni dukaz pomoci obratlovcu). Druhy dukaz Cayleyovy vety (indukci pomoci multinomickych koeficientu a multinomicke vety).

14. prednaska 11.1.2000: Treti dukaz Cayleyovy vety pomoci Prueferova kodovani. Pak konzultace.

leden 2000