Pondeli 12:20 v S3
Prednasejici: J. Kratochvil, P. Valtr
UPOZORNENI: Predmet DMI011 je letos vyucovan pro prvni i druhy rocnik. Vzhledem k prechodu na nove studijni plany se vsak sylaby pomerne vyrazne lisi. Jednoznacne doporucujeme studentum, aby chodili na prednasku a cviceni odpovidajici jejich rocniku.
Literatura:
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, Karolinum, Praha 2002 - ISBN 80-246-0084-6
T. Valla, J. Matousek: Kombinatorika a grafy I. ITI series 2005-260
zde.
23.2.2009 (Kratochvil)
Opakovani pojmu z diskretni matematiky z prvniho rocniku:
grafy, cesty, tahy, sledy, kruznice, souvislost, stromy, kostry, rovinne grafy, triangulace, barevnost grafu.
Filipika o dukazu matematickou indukci - indukcni krok n <-- n-1. Dva priklady
chybneho dukazu indukci (skore stromu a barevnost rovinnych grafu).
Pred pristi prednaskou si zopakujte take pojmy z linearni algebry - vektorove prostory,
linearni zavislost a nezavislost, dimenze, matice, hodnost matic, nasobeni matic,
determinanty.
2.3.2009 (Kratochvil)
Souvislosti s linearni algebrou
Maticovy popis grafu: matice sousednosti.
Prvni vety:
Mocniny matice sousednosti a pocet sledu dane delky (Tvrzeni 3.2.5 z Kapitol).
Pocet koster grafu pomoci determinantu Laplaceovy matice (Veta 7.5.1 z Kapitol).
9.3.2009 (Dan Kral)
Konecne projektivni roviny Definice, rad KPR, konstrukce KPR prvociselneho radu.
16.3.2009 (Kratochvil)
Latinske ctverce Definice, kolmost, NOLC(n)<=n-1.
Veta: Navzajem n-1 ortogonalnich Latinskych ctvercu existuje prave tehdy, kdyz existuje konecna projektivni rovina radu n.
Pocitani poctu koster rekurzivnim rozvojem: t(G)=t(G-e)+t(G:e) (pokud e neni smycka, G je multigraf - vyjimecne pripoustime jak nasobne hrany tak smycky, a kontrakce G:e je multigrafova).
23.3.2009 (Kratochvil)
Hamiltonovske grafy
Definice Hamiltonovske kruznice, postacujici podminky (Oreho, Dirakova a Lovaszova veta, Chvataluv uzaver).
Problem Obchodniho cestujiciho TSP Aproximacni algoritmus
zalozeny na minimalni kostre (funguje pouze pro vahy splnujici
trojuhelnikvoou nerovnost), apr. faktor 2.
Lizatkove grafy Smithova a Thomasonova veta - v grafu, jehoz vsechny vrcholy maji lichy stupen, prochazi kazdou hranou sudy pocet Ham. kruznic. Otevreny problem Mame-li takovy graf dan s jednou Ham. kruznici, existence dalsi Ham. kruznice je zarucena vetou. Avsak neni jasne, zda se dalsi HK da nalezt v polynomialnim case.
30.3.2009 (Valtr)
Toky v sitich
sit, tok, velikost toku, existence max. toku (bez dukazu), rez,
(hlavni) veta o tocich, elementarni rez, kazdy rez obsahuje elementarni rez, dukaz jednodussi nerovnosti ve vete o tocich
6.4.2009 (Valtr)
Toky v sitich (pokracovani); souvislost grafu
nasycena cesta, dokonceni dukazu vety o tocich, Ford-Fulkersonuv algoritmus,
veta o celociselnosti;
hranovy a vrcholovy rez, hranova a vrcholova souvislost, lemma o usich
20.4.2009 (Valtr)
nerovnosti pro vrcholovou a hranovou souvislost pri odebrani hrany,
priklad: odebranim vrcholu se muze vrchovova i hranova souvislost libovolne
zvysit, Ford-Fulkersonova veta, Mengerova veta (zaver dukazu priste)
27.4.2009 (Valtr)
dokonceni dukazu Mengerovy vety, Hallova veta, latinske ctverce: libovolny
latinsky obdelnik lze doplnit na latinsky ctverec
4.5.2009 (Kratochvil)
Vytvorujici funkce
Priklady s bankomatem a jejich reseni pomoci roznasobeni soucinu vhodnych
polynomu.
Mocninna rada, vytvorujici funkce, (jednoznacny) vztah mezi posloupnosti a jeji vytvorujici funkci (Taylorova veta z MA).
Operace s posloupnostmi: soucet dvou posloupnosti, vynasobeni posloupnosti
realnym cislem, vynasobeni posloupnosti polynomem x^r, dosazeni alfa.x za x,
dosazeni x^k za x, derivovani a integrovani, vynasobeni dvou posloupnosti.
Odvozeni vzorecku pro n-te Fibonacciho cislo
Definice zobecneneho kombinacniho cisla (r nad k) pro libovolne realne r,
zobecnena binomicka veta (1+x)^r.
Odvozeni vzorecku pro pocet zakorenenych pestovanych binarnich stromu
na n vrcholech.
11.5.2009 (Kratochvil)
Rovinne grafy
Kresleni grafu do roviny a na povrch sfery, otazka vnejsi steny nakresleni.
Lemma o vytvareni 3-souvislych grafu (je-li G vrcholove 3-souvisly graf s alespon 5 vrcholy, pak existuje hrana, jejiz kontrakce neporusi 3-souvislost).
Lemma o kresleni vrcholove 2-souvislych grafu {v kazdem nakresleni je kazda stena ohranicena grafovou kruznici).
Kuratowskeho veta (graf je rovinny prave kdyz neobsahuje deleni K_5 ani K_{3,3}) a jeji dukaz indukci podle poctu vrcholu (v indukcnim kroku rozlisime pripady podle vrcholove souvislosti grafu = 0, 1, 2, a >= 3).
18.5.2009 (Valtr)
Ramseyovy vety
priklad ukazujici r(3)=6,
5 verzi Ramseyovy vety (zakladni, nesymetricka, dvoubarevna,
vicebarevna, barveni p-tic), dukaz nesymetricke verze,
r(k,l) je mensi nebo rovno (k+l-2 nad k-1),
aplikace barveni p-tic: Erdos-Szekeresova veta o konvexnim k-uhelniku
(viz napr. prvni kapitola
zde)