Zakladni literatura: J. Matousek a J. Nesetril, Kapitoly z Diskretni matematiky, Karolinum 2000. K dostani v prodejne Erudio na Male Strane (dokud bude fungovat), v knihkupectvi v budove MFF v Troji, asi i v Karolinu v Celetne, u Kanzelsbergera na Mustku, ...; k pujceni v knihovne v Karline.

Dve paralelky prednasi jeste dr. Valtr.

O cvicenich a zapoctech. K prednasce je cviceni. Zapocet z neho je nutnou podminkou ke zkousce - to plati pro vsechny typy studia, i pro kombinovane studium. Nepatrite-li do zadneho kruhu (kombinovane, dalkove studium atd.), vyberte si mou prednasku nebo nekterou ze dvou prednasek dr. Valtra a nektere z odpovidajicich cviceni, nejlepe ke stejnemu prednasejicimu.  Zapocet pak dostanete podle pozadavku cviciciho jako ostani studenti. Nemuzete-li chodit na vubec zadne cviceni,  dozvite se pozadavky od mgr. J. Maxove (MS, 3. patro naproti sekretariatu KAM, email jana@kam.ms.mff.cuni.cz), ktera vam bude udelovat zapocet.

Zkousky. Na zkousku si nezapomente index a zkusebni zpravu (se zapsanym zapoctem - na zkousku je potreba zapocet mit). Teminy zkousek:

ctvrtek 3. 1. 2002 (9:00 h v E3, budova menzy v Troji), nutno umet tuto latku z posledni prednasky: Spernerova mnozinova veta o nezavislem systemu (1. dukaz dvojim pocitanim) a dukaz Cayleyho formule pro pocet stromu pomoci obratlovcu (nebo libovolny jiny dukaz).
utery 15. 1. (8:30 h v M2, Karlov) a streda 16. 1. (8:30 h v E5, budova menzy v Troji)
utery 22. 1. (8:30 h v E1, budova menzy v Troji) a streda 23. 1. (8:30 h v T2, Troja)
streda 30. 1. (8:30 h v T2, Troja)
utery 5. 2. (8:30 h v T1, Troja) - tento termin byl presunut ze stredy a spojen s terminem Dr. Valtra.
streda 13. 2. (8:30 h v T2, Troja)

Na zkousky se muzete zapsat do archu, ktere jsou vyveseny v prizemi u vratnice v budove na Malostranskem namesti (novy vchod je z horni casti namesti, tj. zezadu pri prichodu od zastavky tramvaje). Prubeh zkousky: rano od 8:30 pisemka (90 minut), ktera je rozhodujici, odpoledne oznameni vysledku a pripadna ustni cast (v nerozhodnych pripadech). Pocitejte prosim s tim, ze v hojne navstivenych terminech se zkouska muze protahnout. Vzhledem ke komplikacim zpusobenym rekonstrukci malostranske budovy vas prosim o pochopeni pri moznych zmatcich a pripadnem nepohodli.

Pisemka. 4 priklady: 1. na definice (nekolik jednoduchych otazek typu "je tato relace tranzitivni a proc"), 2. napsat vetu s dukazem (napr. vetu o spravnosti hladoveho algoritmu), 3. a 4. trochu slozitejsi vymysleci priklady (napr. "dokazte vetu o 4 barvach" :-); ci spise stredne tezke priklady, jako se delaly na cvicenich).

1. prednaska 2. 10. 2001.  Kapitola 1. Zakladni pojmy a znaceni. Co je Diskretni matematika: uloha o minimalni kostre a o nekonecne mnoha bodech v rovine s celociselnymi vzdalenostmi (vsechny musi lezet na primce). Ciselne obory (N, Z, Q, R a C) a cele casti realnych cisel.   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:  1^2+2^2+3^2+...+n^2 = n(n+1)(2n+1)/6. Dukaz tohoto vzorecku odvozenim (pomoci i^2 = ((i+1)^3-i^3-3i-1)/3). Neusporadana a usporadana dvojice.

2. prednaska 9. 10. 2001. Kartezsky soucin mnozin, binarni relace relace mezi mnozinami X a Y, binarni relace na mnozine X. Relace ekvivalence. Rozklad mnoziny. Souvislost mezi obema strukturami: Relace ekvivalence na X a rozklady X si vzajemne odpovidaji. Priklady relaci ekvivalence. Funkce a zobrazeni. Injekce (proste z.), surjekce (zobrazeni na) a bijekce (vzajemne jednoznacne z.). Skladani funkci. Usporadani na X: castecne a linearni, ostre a neostre. Priklady usporadani (delitelnosti, inkluzi). Hasseho diagram castecneho usporadani. Kapitola 2. Kombinatoricke pocitani. Pocet funkci z [n]  do [m] je m^n. Pocet podmnozin [n] je 2^n.

3. prednaska 16. 10. 2001. Pocet prostych zobrazeni z [n] do [m] je m(m-1)(m-2)...(m-n+1). Permutace mnoziny X, skladani permutaci, zapisy permutaci (dvouradkovy, posloupnosti, sipkovy graf, cyklovy). Sipkovy graf permutace se sklada z disjunktnich cyklu. Pocet permutaci [n] je n!. Binomicke koeficienty: definice, pocet k-prvkovych podmnozin [n] je prave B(n, k), Pascaluv trojuhelnik. Vzorecky: B(n, k) = B(n, n-k), B(n, k) = B(n-1, k)+B(n-1, k-1) a B(n, k) = (n/k).B(n-1, k-1). Binomicka veta, kombinatoricky dukaz. Multinomicke koeficienty a multinomicka veta (bez dukazu). Odhadovani faktorialu: n! > 2^n pro n>3 (indukci). Stirlingova formule n! ~ (2pi.n)^{1/2}.(n/e)^n (bez dukazu :-) )

4. prednaska 23. 10. 2001. Odhad faktorialu integraci: e(n/e)^n < n! < (e^2/4).(n/e)^n. Vyznam asymptotickeho symbolu O. Princip inkluze exkluze (PIE): |A_1 U A_2 U ... U A_n| = |A_1| + |A_2| + ... + |A_n| - ... . Dukaz zapocitanim prispevku prvku sjednoceni na leve strane a na prave strane. Prvni pouziti PIE: problem satnarky. Pravdepodobnost, ze nahodna permutace nema pevny bod jde k 1/e. Druhe pouziti PIE: Eulerova funkce fi(n) (satnarka i fi(n) s dukazem).

5. prednaska 30. 10. 2001. Kapitola 3. Uvod do teorie grafu. Pojem grafu G = (V, E), uplny graf, kruznice, cesta, uplny bipartitni graf, bipartitni graf. Izomorfismus grafu. Tvrzeni: na mnozine [n] je 2^{B(n, 2)} grafu. Tvrzeni: na mnozine [n] je alespon 2^{B(n, 2)}/n! vzajemne neizomorfnich grafu. Podgraf a indukovany podgraf. (Indukovana) cesta, kruznice v grafu. Tah a sled v grafu. Tvrzeni: lze-li dva vrcholy spojit v G sledem, lze je spojit i cestou (v nem obsazenou). Souvisly graf.

6. prednaska 6. 11. 2001. Komponenta souvislosti grafu. Vzdalenost v souvislem grafu, je to metrika. Polomer a prumer grafu. Stupen vrcholu, soucet stupnu je 2|E|, pocet vrcholu licheho stupne je sudy. Skore grafu. Havlova--Hakimiho veta o skore. Prednaska byla zkracena o 30 min. kvuli odjezdu prednasejiciho na sluzebni cestu.

7. prednaska 13. 11. 2001. Eulerovske grafy a jejich charakterizace: G je eulerovsky, prave kdyz je souvisly (az na iz. vrcholy) a ma vsechny stupne sude. Orientovane grafy a orientovane eulerovske grafy. Jejich charakterizace. Formulace problemu kotouce (bez reseni). 2-souvisle grafy. Lemma o usich: G je 2-souvisly, prave kdyz se da vytvorit z kruznice pridavanim usi. Ve 2-souv. grafu lezi kazde dva vrcholy na kruznici (dukaz pomoci lemmatu o usich). Formulace ulohy o jednosmerkach (kazdy 2-souv. graf ma silne souvislou orientaci; bez reseni). Ctyri grafove operace: vyhozeni a pridani hrany, vyhozeni vrcholu, rozdeleni hrany. G je 2-souv., prave kdyz se da vytvorit z K_3 operacemi pridani hrany a rozdeleni hrany.

8. prednaska 20. 11. 2001. Kapitola 4. Stromy. Definice stromu. Kazdy strom s alespon 2 vrcholy ma alespon 2 listy. Veta: pet vzajemne ekvivalentnich definic stromu (1. souv. bez kruznice, 2. kazde 2 vrcholy maji jedinou spojujici cestu, 3. minim. souvisly, 4. maxim. bez kruznice a 5. souv. a |E| = |V|-1). Algoritmus pro rozhodovani izomorfismu stromu, nejprve pro stromy s korenem (pomoci 0-1 kodovani).

9. prednaska 27. 11. 2001. Dokonceni algoritmu pro rozhodovani izomorfismu stromu-pro obecne stromy pomoci centra. Centrum stromu se ziska odlupovanim listu. Kostra souv. grafu, minimalni kostra, problem minimalni kostry. Hladovy (Kruskaluv) algoritmus pro hledani minimalni kostry. Veta: hladovy algoritmus funguje. Kapitola 5. Rovinne grafy. Oblouk v rovine, topologicka kruznice. Rovinne nakresleni grafu. Graf je rovinny, ma-li rovinne nakresleni.

10. prednaska 4. 12. 2001. Stena rov. nakresleni. Pojem souvislosti a obloukove souvislosti podmnozin roviny. Pro otevrene mnoziny oba pojmy splyvaji; bez dukazu.  Priklad souvisle mnoziny, ktera neni obl. souvisla. Neomezena stena rov. nakresleni. Stereograficka projekce: kresleni na sfere dava totez co kresleni v rovine. Uloha za DOM CV: kazdy rov. graf ma rov. nakresleni lomenymi carami. Jordanova veta o kruznici: R^2 \ top. kruznice ma prave dve komponenty; bez dukazu. Tvrzeni: kazda stena v kazdem rov. nakresleni 2-souv. grafu ma za hranici kruznici. Kuratowskeho veta: G je rovinny, prave kdyz neobsahuje jako podgraf ani deleni K_5 ani deleni K_{3, 3}; bez dukazu. Eulerova formule: |V| - |E| + s = 2 pro kazde souv. rov. nakresleni, kde s je pocet sten. Veta: Je-li G = (V, E) rovinny a |V| >= 3, plati |E| <= 3|V| - 6; neni-li navic K_3 podgrafem G, plati dokonce |E| <= 2|V| - 4. Dukaz (ve skriptech je zbytecne slozite). Buno (pridani hran) je nase rov. nakresleni souvisle. Pro stenu S bud deg(S) pocet hran na jeji hranici. Pak deg(S) >= 3 pro kazdou S - pro omezene steny to je zrejme a pro neomezenou stenu je 1 trivialni vyjimka. Secteme stupne sten: 3s <= sum_S deg(S) <= 2|E| a tedy s <= (2/3)|E|. Podle E. formule 2 = |V| -|E| + s <= |V| - |E|/3 a tedy |E| <= 3|V| - 6. Druha nerovnost se dokaze uplne stejne, pouze vyjdeme z lepsiho odhadu deg(S) >= 4 pro kazdou stenu S. Ten je pro omezene steny opet zrejmy (stena nemuze byt trojuhelnik) a pro neomezenou stenu jsou 3 trivialni vyjimky, pro nez dokazovana nerovnost zjevne plati. QED

11. prednaska 11. 12. 2001. Kazdy rov. graf ma vrchol stupne <= 5. Platonska telesa (mnohosteny). Existuje jen techto 5 platonskych teles: 4-sten, 6-sten, 8-sten, 12-sten a 20-sten. Dukaz pomoci Eulerovy formule prevedenim na rovinne grafy. Dualita platonskych teles a pojem dualniho rov. nakresleni. Je-li G* dualni rov. nakresleni k nakresleni G, ma G* tolik koster jako G; bez dukazu. Barveni obecnych grafu, chromaticke cislo grafu, barevnost kruznic, uplnych grafu. Problem barevnosti rov. grafu. Veta o 4 barvach; bez dukazu. Veta o 6 barvach (kazdy rov. graf lze obravit 6 barvami). Veta o 5 barvach priste.

12. prednaska 18. 12. 2001. Dva dukazy vety o 5 barvach: 1. pomoci kontrakci hran (u vrcholu v s 5 sousedy se zkontrahuji dve hrany, ktere spojuji v se dvema sousedy, kteri nejsou spojeni hranou) a 2. pomoci Kempeho retezcu (obarveni se modifikuje tak, aby se na 5 sousedech vrcholu v nejaka barva zopakovala). Kapitola 6. Pocitani dvema zpusoby. Spernerovo geometricke lemma: V kazde skoro-triangulaci s vrcholy obarvenymi barvami 1, 2, a 3, pricemz tri na obvodu vyznacene vrcholy A_1, A_2 a  A_3 maji barvy 1, 2 a 3 a kazdy vrchol na obvodu mezi A_i a A_j ma barvu i nebo j, je trojuhelnikova stena s vrcholy obarvenymi vsemi tremi barvami 1, 2 a 3. Poznamky o aplikacich Sp. geom. lemmatu: Brouwerova veta o pevnem bodu, ucesani koule; bez dukazu.

13. prednaska 8. 1. 2002. Spernerova mnozinova veta: kazdy nezavisly system M podmnozin n-prvkove mnoziny X ma nanejvys B(n, [n/2]) clenu. Dukaz pomoci dvojiho pocitani dvojic (M, R), kde R je maximalni retezec podmnozin mnoziny X a M je prvek lezici soucasne v M a v R.  Kapitola 7. Pocet koster. Cayleyho formule: na mnozine {1, 2, ..., n} je presne n^{n-2} oznackovanych stromu. Dukaz pomoci obratlovcu, tj. bijekce mezi obratlovci (obratlovec=strom+dvojice vrcholu) a zobrazenimi mnoziny {1, 2, ..., n} do sebe.

leden 2002