Vyuka - Martin Klazar

Diskretni Matematika DMI002

Literatura: J. Matousek a J. Nesetril, Kapitoly z Diskretni matematiky, Karolinum 2000 (dotisk 2002). K dostani v prodejne MFF v Troji, v knihkupectvi Karolinum v Celetne, u Kanzelsbergera na Mustku a i jinde. Prednaska pokryje kapitoly 1-7 a z knihy lze studovat samostatne.

Prednaska se kona v pondeli v 10:40-12:10 v poslucharne M1 na Karlove. Dve dalsi paralelky prednaseji dr. P. Valtr a dr. J. Fiala .

Cviceni. K prednasce je cviceni. Zapocet z neho je nutnou podminkou ke zkousce; podminky stanovuje cvicici. Emailove adresy cvicicich k me prednasce: Martin Balek (balek@kam.mff.cuni.cz), Yared Nigoussie (yared@kam.mff.cuni.cz), Petr Skovron (xofon@kam.mff.cuni.cz), Ida Svejdarova (hicsuntidae@yahoo.com).

Informace pro studenty distancniho a kombinovaneho studia. Studovat lze samostatne podle knihy Matouska a Nesetrila, ale neuskodi se na prednasku nekdy zajit podivat (muzete si vybrat libovolnou ze tri paralelek, prednasime zhruba totez). Zapocet je nutnou podminkou ke zkousce i pro tyto typy studia. Doporucuji navstevovat nektere cviceni, vyberte si podle casovych moznosti cviceni k libovolne paralelce. Zapocet pak dostanete podle pozadavku cviciciho jako ostani studenti. Nemuzete-li chodit na zadne cviceni, dozvite se pozadavky od Mgr. Petra Skovrone (xofon@kam.mff.cuni.cz), ktery vam po jejich splneni zapocet udeli.

Konzultacni hodiny jsou v pondeli 16-18 h (zmena z 15-17).

Obsah prednasky

1. prednaska 29. 9. 2003. Kapitola 1. Zakladni pojmy a znaceni. Dve motivacni ulohy: uloha o vecirku (Ramseyova cisla) a uloha o protahovani silnic od snehu (minimalni kostra). Ciselne obory (N,Z,Q,R a C), 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. Matematicka indukce na prikladu - 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6.

2. prednaska 6. 10. 2003. Odvozeni predesleho vzorce z i² = ((i+1)³ - i³- 3i - 1)/3. Kartezsky soucin mnozin, binarni relace, relace mezi mnozinami X a Y, binarni relace na mnozine X. Relace ekvivalence. Rozklad mnoziny. Tridy ekvivalence. Souvislost mezi obema strukturami: Tridy ekvivalence tvori rozklad a naopak rozklad jednoduse definuje 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.

3. prednaska 13. 10. 2003. Kapitola 2. Kombinatoricke pocitani. Pocet zobrazeni z n-prvkove mnoziny do m-prvkove mnoziny je mⁿ, pocet prostych takovych zobrazeni je m(m-1)(m-2)...(m-n+1). Potence n-prvkove mnoziny ma 2ⁿprvku. Permutace a jejich znaceni, pocet permutaci n-prvkove mnoziny jest n!. Sipkovy graf permutace konecne mnoziny se sklada z disjunktnich cyklu. Binomicke koeficienty B(n, k) a jejich vlastnosti. Pocet k-prvkovych podmnozin n-prvkove mnoziny je B(n, k). Pascaluv trojuhelnik

                1
              1   1
            1   2   1
          1   3   3   1
        1   4   6   4   1
                .
                .
                .

pocita binomicke koeficienty B(n, k). Zajimavost (bez dukazu): "Belluv trojuhelnik" (jak se generuje, he!?)

              1
              1   2
            2   3   5
          5   7   10 15
       15 20 27   37   52
                .
                .
                .

pocita Bellova cisla, tj. pocty rozkladu n-prvkove mnoziny. Binomicka veta (kombinatoricky dukaz). Multinomicke koeficienty a multinomicka veta (bez dukazu). Rust faktorialu: Stirlingova formule n! ~ (2.pi.n)^1/2.(n/e)ⁿ (bez dukazu) a zacatek dukazu odhadu e.(n/e)ⁿ< n! < n.e²/4.(n/e)ⁿ.

4. prednaska 20. 10. 2003. Dukaz odhadu e.(n/e)ⁿ< n! < n.e²/4.(n/e)ⁿ. Asymptoticke symboly ~, o a O. Princip inkluze a exkluze (PIE). Pouziti PIE pro problem satnarky: pocet permutaci cisel 1, 2, ..., n bez pevneho bodu je n!.(1 - 1/1! + 1/2! - ... + (-1)ⁿ/n!). Pouziti PIE pro odvozenni formule pro Eulerovu funkci phi(n) (= pocet prir. cisel <n nesoudelnych s n): phi(n) = n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/p_r), kde p_i jsou prvocinitele cisla n (bez dukazu). Kapitola 3. Uvod do teorie grafu. Pojem grafu, G = (V,E).

5. prednaska 27. 10. 2003. Dulezite typy grafu: uplny graf, kruznice, cesta, uplny bipartitni graf, bipartitni graf. Izomorfismus grafu. Tvrzeni: pocet vsech grafu na vrcholove mnozine {1, 2, ..., n} je roven 2^n(n-1)/2 a pocet vzajemne neizomorfnich mezi nimi je 2^{(1-o(1))n^2/2}. Podgraf a indukovany podgraf. (Indukovana) cesta a kruznice v grafu. Souvisly graf, komponenta souvislosti grafu.

6. prednaska 3. 11. 2003. Definice sledu a tahu v grafu. Kazdy sled spojujici dva vrcholy obsahuje cestu spojujici tytez dva vrcholy. Grafova vzdalenost, ma vlastnosti metriky. Polomer a prumer grafu. Stupen vrcholu, skore grafu. Lemma o stupnich: soucet stupnu je dvojnasobek poctu hran. Dusledek: pocet vrcholu licheho stupne je vzdy sudy. Havlova-Hakimiho veta o skore: d₁ <= d₂ <= ... <= d_nje skore grafu, prave kdyz d₁, d₂, ... ,d_{n-d_n-1} , d_{n-d_n} - 1, d_{n-d_n+1} - 1, ..., d_n-1 - 1 je skore grafu. Eulerovske tahy a eulerovske grafy. Charakterizacni veta eulerovskych grafu: Graf bez izolovanych vrcholu je eulerovsky, prave kdyz je souvisly a ma vsechny stupne sude; dukaz priste.-les

7. prednaska 10. 11. 2003. Dukaz charakterizace eul. grafu. Charakterizace orientovanych eul. grafu; bez dukazu. Definice 2-souvislych grafu. Lemma o usich: G je 2-souv., prave kdyz se da vytvorit z kruznice pridavanich uch. Aplikace: ve 2-souv. grafu lezi kazde dva vrcholy na spolecne kruznici. Kapitola 4. Stromy. Definice stromu (souvisly graf bez kruznic). Kazdy strom na alespon dvou vrcholech ma alespon dva listy.

8. prednaska 24. 11. 2003 (17. 11. byl statni svatek). Veta o charakterizaci stromu (5 vzajemne ekvivalentnich definic stromu). Algoritmus pro rozpoznavani izomorfismu stromu (nalezeni centra odtrhavanim listu, zakoreneni stromu v centru a rozhodnuti o izomorfismu pomoci kodovani stromu slovy z 0 a 1).

9. prednaska 1. 12. 2003 Dokonceni izomorfismu stromu: dva stromy s korenem jsou izomorfni (izomorfismem zachovavajicim koren), prave kdyz maji stejne kody. Problem minimalni kostry a "hladovy" algoritmus na jeho reseni; dukaz jeho spravnosti. Kapitola 5. Rovinne grafy. Krivka v rovine. Nakresleni grafu (v rovine) a rovinne nakresleni, rovinne grafy. Neformalni definice steny rov. nakresleni. Obloukova souvislost mnoziny v rovine a obycejna souvislost.

10. prednaska 8. 12. 2003 Poznamky o obycejne a obloukove souvislosti. Definice steny rov. nakresleni R: komponenta (obloukove) souvislosti mnoziny R² - R. Stereograficka projekce (kresleni grafu na sfere se nelisi od kresleni v rovine). Topologicka kruznice a Jordanova veta o kruznici (bez dukazu). K₅a K_3,3 jsou nerovinne grafy. Kuratowskiho veta (bez dukazu). Hranice kazde steny v rov. nakresleni 2-souv. grafu je kruznice (bez dukazu). Eulerova formule: v kazdem souv. rov. nakr. plati |V| - |E| + s = 2. Odhady poctu hran rov. grafu: |E| <= 3|V| - 6 (alespon 3 vrcholy)a |E| <= 2|V| - 4 (alespon 3 vrcholy a bez trojuhelniku). Kazdy rov. graf ma vrchol stupne nejvyse 5.

11. prednaska 15. 12. 2003 Definice radneho obarveni a chromatickeho cisla. Veta o 5 barvach: kazdy rovinny graf se da radne obarvit 5 barvami, 1. dukaz pomoci kontrakci hran a 2. dukaz pomoci Kempeho retezcu. Kapitola 6. Pocitani dvema zpusoby. Spernerovo geometricke lemma: V kazdem (ne nutne radnem) obarveni vrcholu rovinneho nakresleni, jehoz vsechny steny az na vnejsi jsou trojuhelniky a obvod vnejsi steny je kruznice, barvami 1, 2 a 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 vyskytuje trojuhelnikova stena s vrcholy obarvenymi vsemi barvami 1, 2 a 3. Poznamky o dusledcich: Brouwerova veta o pevnem bodu a nemoznost ucesat kouli.

12. prednaska 5. 1. 2004 Spernerova mnozinova veta: maximalni velikost antiretezce podmnozin mnoziny [n]={1, 2, ..., n} je B(n, n/2). Dukaz dvojim pocitanim. Kapitola 7. Pocet koster. Cayleyho veta: cislo k(K_n) = pocet koster uplneho grafu K_n = pocet stromu na mnozine {1, 2, ..., n} je dano vzorcem n^n-2. Dukaz Jima Pitmana podle podkapitoly 7.6 v knize Matouska a Nesetrila, ale ne uplne doslovne. Zde je. Necht l(k, n), 0 <= k <= n-1, je pocet k-lesu na mnozine [n], kde k-les je les (acyklicky graf) na [n], ktery (i) ma k hran, (ii) ma v kazde komponente, jichz je n-k, zvoleny jeden vrchol jako koren a (iii) ma hrany oznaceny cisly 1, 2, ..., k. Ukazeme rekurenci l(k+1, n) = l(k, n)*n*(n-k-1). V k+1-lese T smazeme hranu e={x, y} oznacenou k+1. Komponenta C obsahujici e se tim rozpadne na dve komponenty C' a C''. Nech x je v C', y v C'' a C' obsahuje stary koren C. C' jeji koren ponechame a v C'', ktera o koren prisla, jako koren zvolime y. Vznikne k-les U. Pocet k+1-lesu T, ktere se takto zredukuji na jeden pevny k-les U, je tedy roven poctu dvojic vrcholu (x,y), kde x a y lezi v ruznych komponentach U a y je korenem nejake komponenty k-lesa U. Takovych dvojic ale je presne n*(n-k-1), protoze x lze zvolit libovolne n zpusoby a se zvolenym x pro y mame o jedna mene moznosti, nez kolik ma U komponent (y je korenem, ale nemuze byt korenem komponenty obsahujici x). Tim je rekurence dokazana. Oznacime-li faktor n*(n-k-1) jako f(k, n), diky rekurenci mame l(n-1, n) = l(0, n)*f(0, n)*f(1, n)*...*f(n-2, n) = 1*n^n-1*(n-1)! (0-les je jen jeden). Na druhou stranu ale take mame l(n-1, n) = k(K_n)*n*(n-1)!, protoze n-1-les je strom na [n] s jednim vyznacenym vrcholem (korenem) a hranami oznacenymi 1, 2, ..., n-1. Porovnanim dostavame rovnici n^n-1*(n-1)! = k(K_n)*n*(n-1)!, z niz plyne k(K_n) = n^n-2.

leden 2004