Zakladni literatura: J. Matousek a J. Nesetril, Kapitoly z Diskretni matematiky, Karolinum 2000. K dostani v prodejne Erudio na Male Strane, v knihkupectvi v budove MFF v Troji, asi i v Karolinu v Celetne, u Kanzelsbergera na Mustku, ...; k pujceni v knihovne v Karline. V Celetne se pry prodava skriptove vydani teto knihy (z r. 1996) se slevou.

Prednaska se kona v poslucharne M1 v budove na Karlove v pondeli od 15:40 do 17:10. Planuju probrat kapitoly 1 (Zakladni znaceni), 2 (Kombinatoricke pocitani),  3 (Grafy: uvod), 4 (Stromy), 5 (Rovinne kresleni grafu), 6 (Pocitani dvema zpusoby) a 7 (Pocet koster). Nasleduje prehled dosud probrane latky.

1. prednaska 2. 10. 2000.  Kapitola 1. Zakladni pojmy a znaceni. Ciselne obory (N, Z, Q, R a C), cele casti realnych cisel. Ulozka 1: Pro realne cislo a, ktere neni polocele (tvaru cele c.+1/2), vyjadrete pomoci operace dolni cela cast cele cislo z lezici nejblize a.  Znaceni sumy a soucinu. Mnozinove znaceni: zapisy mnozin, kardinalita, potencni mnozina, podmnozina, prazdna mnozina, sjednoceni, prunik, rozdil, disjunktni mnoziny. Prunik a sjednoceni jsou komutativni, asociativni a vzajemne distributivni operace,  de Morganovy vzorce.  Matematicka indukce, priklad dukazu matem. indukci (n!>2^n pro kazde n>=4). Neusporadana a usporadana dvojice, kartezsky soucin mnozin X a Y, relace R mezi X a Y, relace na X. Reflexivni, symetricke, tranzitivni relace. Relace ekvivalence. Priklad s jablky.

2. prednaska 9. 10. 2000. Relace ekvivalence, priklad ekvivalence: aRb, prave kdyz 3 deli rozdil a-b. Funkce (zobrazeni) f: X -> Y, prosta (injektivni) f., f. na (surjektivni), bijekce. Ulozka 2: X je konecna, pak f: X -> X je prosta, prave kdyz je na. Co se deje pro nekonecnou X?  Skladani funkci. Ulozka 3: Co provadi skladani s injektivitou a surjektivitou. Usporadani, linearni u., ostre u., znazornovani u. Hasseho diagramem. Priklady Hasseho diagramu: ([10], | ), kde | je delitelnost, a (exp({1, 2, 3}), inkluze). Kapitola 2. Kombinatoricke pocitani. Pocet funkci z n-prvkove mnoziny do m-prvkove je m^n, je to vlastne pocet slov delky n nad m-prvkovou abecedou. Pocet vsech podmnozin n-prvkove mnoziny je 2^n.  Pocet podmnozin s lichym i sudym poctem prvku je tyz, 2^{n-1} (viz cviceni).

3. prednaska 16. 10. 2000.  Vzorec pro pocet prostych zobrazeni f: [n] -> [m]. Permutace (konecne) mnoziny  X, vlastnosti sipkoveho grafu permutace (jedna sipka vstupuje a jedna vystupuje; sklada se z disj. cyklu). Zapisy permutaci: jako zobrazeni, posloupnosti, sipkovym grafem, pomoci cyklu. Pocet permutaci n-prvkove mnoziny. Definice binomickeho koeficientu B(n, k). Mnozina o n prvcich ma B(n, k) k-prvkovych podmnozin. Zakladni vlastnosti: B(n, k) = B(n, n-k), B(n, k) = B(n-1, k)+B(n-1, k-1), B(n, k) = (n/k)B(n-1, k-1). Pascaluv trojuhelnik. Binomicka veta: (1+x)^n = B(n, 0)x^0 + B(n, 1)x^1 + ... + B(n, n)x^n; pocitaci dukaz. Ulozka 4: dokazte ji indukci.  Multinomicky koeficient a multinomicka veta; bez dukazu. Priklad: (a+b+c)^3 rozvinuto multinomickou vetou.

4. prednaska 23. 10. 2000. Odhad faktorialu: porovnanim plochy pod grafem funkce log x a plochy stupnoviteho utvaru dostavame nerovnosti integral_1^n log x dx < log 1 + log 2 + ... + log n < integral_2^{n+1} log x dx, z cehoz plyne odhad e.(n/e)^n < n! < (e^2/4).(n/e)^n. Ulozka 5: pridejte ke stupnum trojuhelnicky (lezi pod grafem, log x je konkavni) a zlepsete odhad.  Stirlingova aproximace n! ~ (2pi.n)^{1/2}.(n/e)^n; bez dukazu. Smysl asymptotickeho symbolu ~. Ulozka 6: odhadnete Stirlingem binom. koeficient B(2n,n).   Princip inkluze a exkluze PIE (vyjadreni mohutnosti sjednoceni mnozin mohutnostmi pruniku). Dukaz porovnanim prispevku prvku sjednoceni na obou stranach formule. Problem satnarky: kolik je permutaci cisel 1, 2, ..., n bez pevneho bodu? Je jich n!.(1-1/1!+1/2!-1/3!+...+(-1)^n/n!). Nahodna permutace tedy (pro velke n) nema pevny bod s pravdepodobnosti asi 1/e = 0.36787... Dalsi aplikace PIE: Eulerova funkce fi(n) a vzorec pro ni. fi(n) = pocet cisel 1, 2, ..., n nesoudelnych s n. Vzorec: fi(n) = n.(1-1/p)(1-1/q)...(1-1/s), kde p, q, ... s jsou prvocisla delici n. Bez dukazu.

5. prednaska 30. 10. 2000. Kapitola 3. Uvod do teorie grafu. Definice (konecneho neorientovaneho grafu), mnozinove zadani grafu, obrazkem. Specialni grafy: uplny graf K_n, kruznice C_n, cesta P_n, uplny bipartitni graf K_{m,n}, bipartitni graf (kazdy graf, jehoz vrcholy lze rozlozit na dve casti tak, ze uvnitr zadne z obou casti nelezi hrana). Izomorfismus grafu: G=(V,E) a G'=(V',E,) jsou izom., existuje-li bijekce f: V->V' takova, ze {a,b} je hrana G, prave kdyz {f(a),f(b)} je hrana G'. Priklad: C_5 je izomorfni svemu doplnku. Tvrzeni: pocet vsech grafu na mnozine {1, 2, ...,n} je 2^{B(n,2)} a pocet vzajemne neizomorfnich z nich je alespon 2^{B(n,2)}/n!. Podgraf a indukovany podgraf. (Indukovana) cesta a kruznice v grafu. Souvisly graf a komponenta souvislosti. Vzdalenost v souvislem grafu (=delka nejkratsi spojujici cesty). Stupen vrcholu a skore grafu. Tvrzeni: soucet stupnu vrcholu je roven dvojnasobku poctu hran. Dusledek: pocet vrcholu licheho stupne je sudy.

6. prednaska 6. 11. 2000. Veta o skore: posloupnost D=(d_1, d_2, ..., d_n) (usporadana vzestupne) je skore grafu, prave kdyz posloupnost D' vznikla vyhozenim posledniho clenu  d_n a zmensenim d_n predchozich clenu o 1 je skore grafu. Ulozka7: je doplnek nesouvisleho grafu nesouvisly, souvisly nebo nekdy souvisly a nekdy nesouvisly?   Tah v grafu, uzavreny tah, eulerovsky tah. Graf je eulerovsky, ma-li uzavreny eul. tah (=da se nakreslit jednim tahem, pricemz skoncime tam, kde jsme zacali). Veta o eul. grafech: graf je eulerovsky <-> je (az na izolovane vrcholy) souvisly a ma vsechny stupne sude. Dukaz indukci vyhozenim hran nejake kruznice. Pojem orientovaneho grafu. Orientovane eul. grafy. Veta: or. graf je eulerovsky <-> jeho symetrizace (=zapomeneme na orientaci) je (az na iz. vrcholy) souvisla a u kazdeho vrcholu se vstupni stupen rovna vystupnimu. Dukaz je stejny. Problem kotouce.

7. prednaska 13. 11. 2000. Problem kotouce pro k=3 (cyklicke poradi 00011101 dava vsechny slova delky 3). 2-souvisle grafy (alespon 3 vrcholy, zustava souvisly i po vyhozeni lib. vrcholu). Operace vyhozeni a pridani hrany, deleni hrany, vyhozeni vrcholu. 2-souv. graf je souv. i po vyhozeni hrany. G je 2-souv. <-> G%e je 2-souv. . Lemma o uchach: G je 2-souv. <-> G lze vytvorit z kruznice pridavanim uch. Tvrzeni: ve 2-souv. grafu lezi kazde dva vrcholy na spolecne kruznici. Kapitola 4. Stromy. Definice stromu: souv. graf bez kruznice. Existence listu a indukce podle listu. Pet ekvivalentnich definic stromu: 1. G je strom. 2. Kazde 2 vrcholy lze spojit prave jednou cestou. 3. G je minimalni souvisly. 4. G je maximalni bez kruznice. 5. G je souvisly a |V|=|E|+1. Dukaz priste.

8. prednaska 20. 11. 2000. Dukaz ekvivalence 5 definic stromu. Pojem korenoveho stromu. Izomorfismus korenovych stromu. Algoritmus pro rozpoznavani izom. korenovych stromu pomoci kodu. Tvrzeni: dva k. stromy jsou izom. <-> maji tyz kod. Naznaceni postupu pro obecny strom, podrobnosti priste.

9. prednaska 27. 11. 2000. Centrum grafu: mnozina vrcholu s nejmensi excentricitou, pricemz excentricita vrcholu je nejvetsi vzdalenost do jineho vrcholu. Tvrzeni: 1. centrum se izomorfismem zachovava a 2. centrum stromu, coz je jeden vrchol nebo dva sousedni, se ziska odtrhavanim listu. Dokonceni algoritmu pro izomorfismus stromu. Kostra grafu, problem minimalni kostry v grafu s ohodnocenymi hranami. Kruskaluv ("hladovy") algoritmus pro nalezeni minimalni kostry a dukaz jeho spravnosti. Kapitola 5. Rovinne grafy. Rovinne nakresleni grafu. Graf je rovinny, ma-li rovinne nakresleni. Stena rovinneho nakresleni. Exkurz do topologie: pojem souvislosti, obloukove souvislosti a priklad souvisle mnoziny v rovine, ktera neni obloukove souvisla.

10. prednaska 4. 12. 2000. Kazde rovinne nakresleni ma prave jednu neomezenou stenu. Stereograficka projekce (bijekce mezi sferou bez bodu a rovinou). Ulozka 8: v rov. nakreslenich se lze omezit na oblouky tvorene lomenymi carami.  Topologicka kruznice (uzavrena krivka), Jordanova veta: kazda topologicka kruznice ma vnitrek a vnejsek; bez dukazu. Dusledek: K_5 i K_{3,3} jsou nerovinne grafy. Kuratowskiho veta: graf je nerovinny <-> obsahuje jako podgraf deleni K_5 nebo deleni K_{3,3}; bez dukazu. Tvrzeni: hranice steny 2-souv. grafu je kruznice. Euleruv vzorec: v souv. rov. nakreslenich plati, ze pocet vrcholu - p. hran + p. sten = 2. Platonska telesa cili konvexni mnohosteny, jejichz steny jsou prav. k-uhelniky a u jejichz kazdeho vrcholu se styka tyz pocet sten: 4-sten, 6-sten, 8-sten, 12-sten a 20-sten. Veta: jina platonska telesa neexistuji. Odhady na pocet hran rov. grafu, dukaz priste.

11. prednaska 11. 12. 2000. Tvrzeni: rov. graf s n>2 vrcholy ma nejvyse 3n-6 hran v obecnosti a nejvyse 2n-4, neobsahuje-li trojuhelnik. Dusledek: kazdy rov. graf ma vrchol stupne nejvyse 5. Barveni grafu, chromaticke cislo: nejmensi pocet nezavislych mnozin, na nez lze rozlozit vrcholovou mnozinu. Veta o 4 barvach, bez dukazu. Veta o 5 barvach: kazdy rov. graf ma chromaticke cislo nejvyse 5; dukaz pomoci kontrakci hran a dukaz pomoci Kempeho retezcu. Kapitola 6. Pocitani dvema zpusoby. Spernerovo lemma: v (ne nutne radnem) obarveni vrcholu rovinneho nakresleni, jehoz vsechny steny az na vnejsi jsou trojuhelniky a obvod vnejsi steny je kruznice, barvami 1, 2, 3, pricemz na obvodu jsou vyznacene tri vrcholy A_i barvy i=1, 2, 3 a obvodove vrcholy lezici mezi A_i a A_j maji barvu i nebo j, se vzdy vyskytuje trojuhelnikova stena s vrcholy obarvenymi 1, 2, 3. Dukaz priste.

12. prednaska 18. 12. 2000. Dukaz Spernerova geometrickeho lemmatu. Spernerovo mnozinove lemma: jsou-li X_1, X_2, ..., X_k podmnoziny mnoziny {1, 2, ..., n} a zadne dve z nich nejsou v inkluzi, plati k <= B(n, n/2). Dukaz pomoci pocitani dvema zpusoby. Grafy bez ctyrcyklu: ma-li G n vrcholu a neobsahuje-li jako podgraf K_{2,2}=C_4, ma G nejvyse (n^{3/2}+n)/2 hran. Dukaz pocitanim dvema zpusoby a pomoci Cauchy-Schwarzovy nerovnosti, jez byla uvedena bez dukazu.

13. prednaska 1. 1. 2001. nekona se, je Novy rok.

14. prednaska 8. 1. 2001. odpada, prednasejici je na konferenci.

prosinec 2000