Literatura: J. Matousek a J. Nesetril, Kapitoly z Diskretni matematiky, Karolinum 2000. K dostani v Karolinu v Celetne, u Kanzelsbergera na Mustku. (Predchozi vydani Matfyzpress, 1996).

Prednaska se kona v utery v 12:20-13:50 v poslucharne F1 na Karlove. Dve dalsi paralelky prednaseji  dr. P. Valtr a dr. J. Fiala .

Historickou anomalii letosniho semestru je jeho zkraceni o 2 tydny vzhledem k pozdejsimu zahajeni vyuky v dusledku skod na budovach MFF zpusobenych povodni v Praze 10.-13. srpna 2002. Budeme tedy mit o 2 prednasky mene.

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 kolegu Valtra a Fialy 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 (jana@kam.mff.cuni.cz), ktera vam po jejich splneni zapocet udeli.

Zkousky. Pisemka na 90 minut se 4 priklady, ukazka jedne varianty je zde. Znamka je urcena vasim vykonem v pisemce, jen v nerozhodnych pripadech dostanete ustni otazku.
Predtermin: 10.1. 2003 od 9h v F2. Na zkousku je treba mit index (a zkusebni zpravu) se zapoctem.
Terminy ve zkouskovem obdobi: vzdy v patek od 9 h (17.1., 24.1., 31.1., 7.2., 14.2. 2003) v T1, termin je spolecny pro vsechny 3 paralelky. Zapis na zkousky je elektronicky, predmet DMI002 je veden pod J. Fialou, zkousime ovsem vsichni tri, J. Fiala, P. Valtr a ja.
 

PO ZKOUSENI 20.12.02 BYLY V F2 NALEZENY HODINKY, JSOU U DR. VALTRA.

Planovany obsah prednasky

Obsah prednasky je clenen podle jednotlivych kapitol knihy Matouska a Nesetrila Kapitoly z Diskretni matematiky.

1. kapitola: zakladni pojmy a jejich vlastnosti, znaceni: mnoziny, potencni mnozina, matematicka indukce, usp. a neusp. dvojice, kart. soucin, relace, vlastnosti relaci,
zobrazeni, druhy zobrazeni

2. kapitola: usporadani, permutace a faktorialy, kombinacni cisla, binomicka veta, princip inkluze a exkluze (PIE), priklady na pouziti PIE

3. kapitola: uvod do teorie grafu: pojem grafu, vyznacne typy grafu, izomorfismus grafu, podgrafy, souvislost, komponenty, princip sudosti, veta o skore, kresleni grafu
jednim tahem, nektere grafove operace, 2-souvisle grafy a jejich zakl. vlastnosti, lemma o usich

4. kapitola: definice stromu a jejich zakl. vlastnosti, ruzne charekteristiky stromu, izomorfismus stromu (kodovani 0-1 posloupnostmi), kostra grafu, Kruskaluv
(hladovy) algoritmus pro nalezeni minimalni kostry souvisleho grafu s ohodnocenymi hranami

5. kapitola: rovinne grafy: definice rov. grafu, steny nakresleni, Jordanova veta o kruznici, nerovinnost K_5 a K_{3,3}, Euleruv vzorec a jeho dusledky, barveni map a
grafu, problem 4 barev, dukaz vety o 5 barvach

6. kapitola: princip dvojiho pocitani a jeho pouziti

7. kapitola: veta o poctu koster uplneho grafu.

Skutecny obsah prednasky

1. prednaska 15. 10. 2002. Kapitola 1. Zakladni pojmy a znaceni. Ciselne obory (N, Z, Q, R a C), cele a zlomkove 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. Matematicka indukce na prikladu - 1^2+2^2+3^2+...+n^2 = n(n+1)(2n+1)/6 - a obecne. Uloha: dokazte tento vzorecek odvozenim pomoci vyjadreni i^2 = ((i+1)^3-i^3-3i-1)/3. Usporadana dvojice. Kartezsky soucin dvou (i vice) mnozin, binarni relace mezi mnozinami X a Y, binarni relace na mnozine X. Relace ekvivalence: reflexivni, symetricka a tranzitivni binarni relace na X. Rozklad mnoziny X.

2. prednaska 22. 10. 2002. Souvislost mezi relacemi ekvivalence na X a rozklady X. Zobrazeni a funkce: proste, surjektivni, bijektivni. Pro konecnou X je zobrazeni z X do X proste, prave kdyz je na. Castecna usporadani, ostra a neostra, linearni usporadani. Hasseho diagram. Kapitola 2. Kombinatoricke pocitani. Pocet zobrazeni z n-prvkove mnoziny do m-prvkove, pocet prostych takovych zobrazeni. Pocet prvku potencni mnoziny. Permutace a jejich znaceni. Sipkovy graf permutace konecne mnoziny se sklada z disjunktnich cyklu.

3. prednaska 29. 10. 2002. Pocet permutaci n-prvkove mnoziny je n!. Binomicke koeficienty B(n, k) a jejich vlastnosti. Pocet k-prvkovych podmnozin n-prvkove mnoziny je B(n, k). Binomicka veta (kombinatoricky dukaz). Multinomicke koeficienty a multinomicka veta. Rust faktorialu: Stirlingova formule (bez dukazu). Formulace principu inkluze a exkluze a jeho dukaz.

4. prednaska 5. 11. 2002. Pouziti PIE v problemu satnarky: Pocet permutaci cisel 1, 2, ..., n bez pevneho bodu je n!.(1 - 1/1! + 1/2! - ... + (-1)^n/n!). Jina aplikace: vzorec pro pocet prirozenych cisel mensich ci rovnych n a nesoudelnych s n (bez dukazu). Kapitola 3. Uvod do teorie grafu. Zakladni pojmy a struktury: graf, uplny graf, kruznice, cesta, uplny bipartitni graf, bipartitni graf. Izomorfismus grafu. Podgraf a indukovany podgraf. (Indukovana) cesta a kruznice v grafu. Souvisly graf, komponenta souvislosti.

5. prednaska 12. 11. 2002. Definice sledu a tahu. Kazdy sled spojujici vrcholy a a b obsahuje cestu spojujici a a b. Vzdalenost v souv. grafu (je to metrika), prumer a polomer grafu. Stupen vrcholu. Soucet stupnu je dvojnasobek poctu hran -> pocet vrcholu licheho stupne je sudy. Skore grafu. Veta o skore grafu
(Havel-Hakimiho veta). Kresleni jednim tahem, eulerovske grafy. Veta o eulerovskych grafech (G je eulerovsky, prave kdyz je az na izolovane vrcholy souvisly a ma vsechny stupne sude).

6. prednaska 19. 11. 2002. Poznamky k minule prednasce: v dukazu vety o skore nevadi, kdyz n <= 3. Zopakovani dukazu vety o eulerovskych grafech. Kralovecke  mosty. Variace na eulerovske grafy: neuzavreny eulerovsky tah a eulerovske orientovane grafy. Problem kotouce (jen formulace). 2-souvisle grafy. Lemma o usich: G je 2-souvisly, prave kdyz se da vytvorit z kruznice opakovanym pridavanim usi. Pouziti tohoto lemmatu: (1) uloha o jednosmerkach (bez dukazu, ktery je lehky) a (2) kazde dva vrcholy 2-souvisleho grafu lezi na kruznici.

7. prednaska 26. 11. 2002. Dokonceni dukazu (2) z minula. Kapitola 4. Stromy. Definice stromu (souvisly graf bez kruznic). Kazdy strom s alespon dvema vrcholy ma alespon dva listy (vrcholy stupne 1). Graf je stromem tehdy a jen tehdy, kdyz je stromem po vyhozeni libovolneho  vrcholu stupne 1. Pet ekvivalentnich definic stromu: G je strom <-> kazde dva vrcholy G lze spojit prave jednou (a jen jednou) cestou <-> G je minimalni souvisly graf (tj. je souvisly, ale po vyhozeni libovolne hrany se rozpadne) <-> G je maximalni graf bez kruznice (tj. neobsahuje kruznici, ale spojeni libovolnych dvou nesousednich vrcholu novou hranou kruznici vytvori) <-> G je souvisly a |E(G)| = |V(G)| - 1. Zacatek popisu algoritmu pro rozeznavani izomorfismu stromu - odtrhavanim listu nalezneme centrum stromu, ktere se sklada z jednoho vrcholu nebo ze dvou sousednich vrcholu.

8. prednaska 3. 12. 2002. Lexikograficke usporadani 0-1 slov, dokonceni popisu algoritmu pro izomorfismus stromu. Kostra, problem minimalni kostry. Kruskaluv cili hladovy algoritmus: hrany grafu G probirame v poradi podle vzrustajici vahy a hranu pridame, prave kdyz s tim, co uz mame, nevytvori kruznici. Na konci mame minimalni kostru. Dukaz spravnosti Kruskalova algoritmu. Kapitola 5. Rovinne grafy. Pojem rovinne krivky.

9. prednaska 10. 12. 2002. Definice rovinneho grafu: reprezentace vrcholu body v rovine a hran nekrizicimi se krivkami. Otevrena rovinna mnozina a jeji souvislost, komponenty souvislosti. Stena rovinneho nakresleni. G je rovinny <-> ma rov. nakresleni lomenymi carami (bez dukazu). Kresleni na sfere-stereograficka projekce. Topologicka kruznice a Jordanova veta o kruznici (bez dukazu). Kuratowskiho veta: G je rovinny <-> neobsahuje jako podgraf ani deleni K_5 ani deleni K_{3,3} (bez dukazu). Eulerova formule: Pro kazde nakresleni souvisleho rov. grafu G=(V,E) plati |V| - |E| + s = 2, kde s je pocet sten; dukaz indukci podle |E|. Hranice kazde steny v kazdem nakresleni rov. 2-souv. grafu je kruznice (bez dukazu, ktery je lehky). Definice platonskeho telesa. Veta: Platonskymi telesy jsou pouze 4-sten (pyramida), 6-sten (krychle), 8-sten, 12-sten a 20-sten (bez dukazu). Definice dualniho grafu.

10. prednaska 17. 12. 2002. Rovinne grafy peti platonskych teles. Veta: rovinny graf s n >= 3 vrcholy ma nejvyse 3n-6 hran; neobsahuje-li trojuhelnik, ma nejvyse 2n-4 hran. Dusledky: K_5 a K_{3,3} nejsou rovinne, kazdy rov. graf ma vrchol stupne nejvyse 5. Obarveni a radna obarveni grafu. Veta o 5 barvach (kazdy rov. graf ma barevnost nejvyse 5), dukaz pomoci Kempeho retezcu. Kapitola 6. Pocitani dvema zpusoby. Formulace Spernerova geometrickeho lemmatu (barveni skorotriangulace tremi barvami), dukaz priste.

11. prednaska 7. 1. 2003. Dukaz Spernerova geometrickeho lemmatu, strucne o aplikacich (Brouwerova veta o pevnem bodu). Spernerova mnozinova veta: kazdy antiretezec na n-prvkove mnozine ma nejvyse B(n, [n/2]) mnozin. Kapitola 7. Pocet koster. Dukaz Cayleyho formule (pocet koster grafu K_n je n^{n-2}) pomoci obratlovcu.

leden 2003