Prednaska ctvrtek 12:20 v M1
Literatura:
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, Karolinum, Praha 2002 - ISBN 80-246-0084-6
Kombinovane studium konzultace po osobni dohode s prednasejicim, pozadavky ke zkousce stejne jako pro studenty denniho studia. Zapocet lze ziskat dvema zpusoby - 1) vyberte si nektere cviceni, na kterem si napisete zapoctove pisemky, nebo 2) obratte se na cviciciho Mgr. Kazdu, ktery vam da sadu prikladu k domacimu vyreseni.
1.10.2009
Opakovani zakladnich pojmu matematiky:
operace s mnozinami, operace s vyroky, kvantifikatory, metody dukazu.
Dukaz matematickou indukci
8.10.2009
Axiomy teorie mnozin, relace a veta o ekvivalenci.
(prednasel prof. Nesetril)
15.10.2009
Prednaska se nekonala, misto ni byla Matematicka analyzaNaopak 19.11. a 26.11. budeme mit
po dvou prednaskach DM - od 9:00 a od 12:20, obe v M1!!!!!!!!!!!!!
22.10.2009
Konstrukce prirozenych cisel v teorii mnozin rekurzivne - 1) 0 je reprezentovana prazdnou mnozinou, 2) pokud n je
mnozina reprezentujici prirozene cislo n, pak n u {n} reprezentuje cislo n+1.
Zobrazeni Definice, vlastnosti - zobrazeni prosta, na, bijekce. Skladani zobrazeni.
Konecne mnoziny Mnozina je konecna, pokud z ni existuje bijekce na nejake prirozene cislo (presneji na mnozinu
reprezentujici nejake prirozene cislo). Toto cislo je urcene jednoznacne a nazyva se mohutnost mnoziny.
Kombinatoricke pocitani Pocet zobrazeni n-prvkove mnoziny do m-prvkove mnoziny je m^n.
29.10.2009
Kombinatoricke pocitani: Pocet prostych zobrazeni n-prvkove mnziny do m-prvkove, pocet bijekci mezi stejne velkymi mnozinami, permutace.
Pocet podmnozin n-prvkove mnoziny. Pocet k-prvkovych podmnozin n-prvkove mnoziny - kombinacni cisla "n nad k". Zakladni vztahy.
Na cviceni bude probrana binomicka veta a pocty podmnozin se sudym (lichym) poctem prvku.
5.11.2009
Ke kombinacnim cislum Pocet reseni rovnice x1+x2+...xk=n, pocet nejkratsich cest v mrizove siti.
Odhady pro faktorial Veta 3.4.1 a 3.4.4, Stirlingova formule bez dukazu.
Princip inkluze a exkluze Veta 3.6.2
12.11.2009
Princip inkluze a exkluze Veta 3.6.2 podrobneji - oba dukazy
(indukci a pocitanim). Problem satnarky neboli pocet permutaci
bez pevneho bodu, jako aplikace PIE.
19.11.2009
Castecne usporadane mnoziny Definice (castecneho) usporadani, linearniho usporadani, primeho naslednika, minimalni, maximalni, nejmensi a nejvetsi prvky. Rozsireni a vnoreni.
Retezce a nezavisle mnoziny.
Veta 2.1.4 o primych naslednicich v konecnych mnozinach.
Veta 2.2.3 o existenci maximalnich a minimalnich prvku.
Veta 2.2.1 o rozsireni na linearni usporadani.
Znazornovani castecnych usporadani Hasseovym diagramem.
Veta 2.3.2 o vnorovani do krychli (tj. do usporadani inkluzi).
Veta 2.4.5 o Dlouhem, Sirokem (a Bystrozrakem).
Veta 2.4.6 (Erdos-Szekeres) Kazda posloupnost prirozenych cisel delky n^2+1 obsahuje monotonni podposloupnost delky aspon n+1.
26.11.2009
Grafy Definice grafu, priklady dulezitych grafu - uplne, uplne bipartitni, kruznice, cesty. Podgrafy a indukovane podgrafy grafu. Sledy, tahy a cesty.
Isomorfismus grafu a odhad poctu neizomorfnich grafu na n vrcholech.
Komponenty souvislosti, souvisle grafy
Eulerovske grafy - kresleni grafu jednim uzavrenym tahem.
Princip sudosti soucet stupnu vrcholu = dvojnasobek poctu hran, a tedy pocet vrcholu licheho stupne je vzdy sudy.
Skore grafu Jak pozname, ze posloupnost priroyenych cisel je posloupnosti stupnu vrcholu nejakeho grafu.
Stromy jsou souvisle acyklicke grafy. Pet dalsich ekvivalentnich definic stromu.
3.12.2009
Stromy a kostry
Pocet stromu na n-prvkove mnozine je n^{n-2}- Veta 8.1.1, dukaz pres obratlovce a grafy zobrazeni.
Hledani minimlani kostry, ukazali jsme Kruskaluv algoritmus 5.3.3 a dokazali jeho spravnost.
17.12.2009
Stromy Izomorfismus stromu pres kodovani (nejprve zakorenene stromy,
pote Veta o centru a kodovani obecnych stromu).
Rovinne grafy Definice, Jordanova veta o kruznici (tedy o jenoduche uzavrene jrivce v rovine, bez dukazu), Kuratowskeho veta, nerovinnost grafu K_5 a K_3,3.
7.1.2010
Pokracovani rovinnych grafu Euleruv vztah - Tvrzeni 6.3.1. Horni odhad na pocet hran rovinneho grafu s n vrhcoly - Tvrzeni 6.3.3. Dusledek o existenci vrcholu stupne nejvyse 5. Definice barevnosti grafu. Dualni graf k rovinnemu nakresleni. Barveni map a barveni vrcholu rovinneho grafu. Veta 6.4.3 o barveni rovinnych grafu 5 barvami.