Diskrétní matematika DMI002, zimní semestr 2010/2011 (P. Kolman)


Místo a čas: Posluchárna S3 na Malé Straně (3. patro), úterý 9:00.

Kromě toho se konají ještě dvě další přednášky z DM se stejným obsahem (tzv. paralelky), na kterých přednáší M. Mareš a O. Pangrác.

Doporučená literatura: J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky

Konzultační hodiny: Po předchozí emailové dohodě (prijmeni@kam.mff.cuni.cz).

Cvičení a zápočet: Veškeré informace o cvičeních, včetně podmínek pro udělování zápočtu, se dozvíte od svých cvičících, viz. rozvrh v SISu. Pro procviceni doporucuji Sbirku prikladu.

Minulé přednášky

prednaska 12.10.
Kartézský součin množin. Relace (definice, příklady, reprezentace, zvláštní vlastnosti [reflexivní, symetrická, antisymetrická, tranzitivní], skládání). Funkce jako zvláštní relace (definice, příklady, zlváštní vlastnosti [prostá ap.], skládání). Počet všech funkcí z množiny X do množiny Y, počet všech podmnožin množiny, počet všech lichých podmnožin.
prednaska 19.10.
Prosta zobrazeni, faktorial a permutace, kombinacni cislo, souvislost s poctem podmnozin dane velikosti. Priklad na pocet celociselnych nezapornych reseni rovnice m=i_1+..+i_r. Vlastnosti kombinacnich cisel a dokazali binomickou vetu.
prednaska 26.10.
Dva male priklady na pouziti binomicke vety (x=1 -> pocet vsech podmnozin je 2^n; x=-1 -> pocet lichych podmnozin = pocet sudych podmnozin). Reflexivni, symetricke, antisymetricke a tranzitivni relace (definice tez pomoci pojmu inverzni relace a "nejmensi reflexivni relace"), pojmy ekvivalence, usporadani a linearni usporadani. U ekvivalence jsme se bavili o tridach ekvivalce dane nejakym prvkem a ukazali, ze tvori rozklad mnoziny. U usporadani jsme zavedli pojem bezprostredni predchudce (pro konecne mnoziny) a formulovali (zatim bez dukazu) vetu o reprezentaci usporadani jen pomoci bezprostrednich predchudcu.
prednaska 2.11.
Dokonceni dukazu vety o CUM a bezprostrednich predchudcich. Hasseuv diagram. Veta o zuplnovani CUM a veta o vnorovani CUM do (2^X,\subseteq). Min/max a nejmensi/nejvetsi prvek, a antiretezec a retezec v CUM.
prednaska 9.11.
Veta o Dlouhem a Sirokem a Erdosovo-Szekeresovo lemma o monotonni podposloupnosti. Zacatek pravdepodobnosti, proc se o ni bavit, diskretni pstni prostor, priklady, veta o uplne psti, nezavisle jevy.
prednaska 16.11.
Zaskok - prednasel kol. Pangrac - pravdepodobnost.
prednaska 23.11.
Uvod ke grafum. Dulezite grafy (uplne, cesta, cykly). Isomorfismu grafu, pocet neisomorfnich grafu na n vrcholech (dolni odhad). Podgrafy grafu (cesta v grafu, ...), indukovane podgrafy. Souvislost. Vzdalenost v grafu. Reprezentace matici sousednosti. Tvrzenim o vyznamu mocniny matice sousednosti (dukaz za domaci ukol, ve skole velka napoveda).
prednaska 30.11.
Pokracovani grafu. Eulerovske grafy (vcetne zminky o obdobe pro orientovane grafy). Stromy (lemma o listu a lemma o postupne vystavbe stromu; zmeni vety o peti ekvivalentnich charakterizacich). Zavedeni operaci odebrani vrcholu, hrany, pridani hrany, rozdeleni hrany. Upozornoval jsem na okraj, ze ne vzdy se orientovane grafy chovaji "stejne" jako neorientovane (coz by se na zaklade veci kolem euleroskych grafu mohlo zdat), napr. hledani hranove disjunktnich cest pro dve dvojice vrcholu a-b, c-d je "lehke" pro neorientovane, ale "tezke" pro orientovane grafy.
prednaska 7.12.
Dokonceni stromu (pet ekvivalentnich vyjadreni), kostra. Rovinne grafy: oblouk (strucna zminka o lomenicich), nakresleni, rovinne nakresleni, rovinne grafy, topologicka kruznice, komponenty obloukove souvislosti, zmeni Jordanovy vety.
prednaska 14.12.
Eulerova formule o poctu vrcholu, hran a sten rovinneho nakresleni rovinneho grafu. S jeji pomoci odhad na maximalni pocet hran v rovinnem grafu (a v rovinnem grafu bez trojuhelniku). Bez dukazu Kuratowskeho vetu. Pravidelne mnohosteny, korespondence (postupne pres jejich kresleni na sferu a pomoci sterograficke projekce i do roviny), s rovinnymi grafy. Zacatek dukazu, proc nejsou zadna jina Platonska telesa, nez tech pet.
prednaska 4.1.2011
Problem ctyr barev, jak souvisi s barvenim grafu (pojem dualniho grafu pro rovinne grafy). Dukaz vety o peti barvach. Dokonceni dukazu o Platonskych telesech z predesle prednasky.