Zkousky: Kdo chce prijit na zkousku do 24.5., napiste email na valtr zavinac kam tecka mff atd.
Literatura:
J. Matoušek, J. Nešetřil: Kapitoly z diskretní matematiky
T. Valla, J. Matoušek: Kombinatorika a grafy I. ITI series 2005-260
ke stažení zde
Email: honza/valtr-zavinac-kam.mff.cuni.cz
Prednaska 25.2. (P.Valtr):
Toky v sitich: sit, tok, velikost toku, rez, minimalni rez.
Existence max. toku (bez dukazu), (hlavni) veta o tocich.
Elementarni rez, kazdy rez obsahuje elementarni rez.
Vylepsujici cesta ze zdroje do nej. vrcholu.
Pozorovani: Pokud ex. vylepsujici cesta ze z do s, potom tok neni maximalni.
Nastin Ford-Fulkersonova algoritmu na nalezeni max. toku.
Prednaska 4.3. (J.Kratochvil):
Dokonceni dukazu vety o tocich (za predpokladu existence max. toku).
Veta o celociselnosti.
Dukaz existence max. toku.
System ruznych reprezentantu, Hallova veta (dukaz pomoci vety o tocich).
Prednaska 11.3. (P.Valtr):
Vrcholovy a hranovy rez, vrcholova a hranova souvislost, priklady.
Po odebranim hrany nebo vrcholu hranova i vrcholova souvislost zustane zachovana nebo klesne o 1.
Ford-Fulkersonova veta.
Prednaska 18.3. (P.Valtr):
Mengerova veta. Vrcholova souvislost je mensi nebo rovna hranove souvislosti (pro libovolny graf).
Lemma o usich (= usate lemma).
Prednaska 25.3. (J.Kratochvil):
Blokova struktura grafu; priklad pouziti: kazdy
graf s maximalnim stupnem 3 ma orientaci s maximalnim vystupnim stupnem 2.
Lemma o kontrakci v 3-souvislem grafu.
1.4. Velikonoce
Prednaska 8.4. (P.Valtr):
Definice oblouku, rovinne grafy, rovinne nakresleni grafu,
definice steny a topologicke kruznice, Jordanova veta o topologicke kruznici
(bez dukazu), K_5 a K_3,3 nejsou rovinne grafy, G rovinny <==> kazde jeho
deleni je rovinne, Kuratowskeho veta: G rovinny <==> G neobsahuje deleni K_5
ani deleni K_3,3 (implikace zleva doprava vyplyva z predchoziho, implikace
zprava nedokazovana), Euleruv vztah pro souvisle(!) rovinne grafy.
Barveni polit. map a rovinnych grafu, vztah mezi nimi, veta o 4 barvach (bez dukazu,
je velmi slozity).
Prednaska 15.4. (P.Valtr):
Dukaz vety o 5 barvach.
Priklad: z 6 osob se tri navzajem znaji nebo tri se navzajem neznaji (predpokladame zde, ze relace "znat se" je symetricka); Ramseyovy vety: symetricka verze, nesymetricka verze, dvoubarevna verze; zavedeni cisel r(k,l) a r(k)=r(k,k).
Prednaska 22.4. (J.Kratochvil):
Exponencialni horni odhad velikosti Ramseyovych cisel (dolni exponencialni
odhad probiran na cviceni). Ramseyova veta pro barveni p-tic k barvami.
Schurova veta a s ni souvisejici odhad r_k(3)\le 1+e.k!.
Aplikace Ramseyovy vety: Erdos-Szekeresova veta o konvexnich
mnohouhelnicich.
Latinske ctverce - uvod (pokracovani na prespristi prednasce).
Prednaska 29.4. (P.Valtr):
Vytvorujici funkce: uvod, operace s posloupnostmi.
Odvozeni vzorce na vypocet n-teho Fibonacciho cisla.
Binomicka a zobecnena binomicka veta, pocet binarnich stromu.
Prednaska 6.5. (J.Kratochvil):
Veta: NOLC(n) <= n-1.
Definice KPR, rad roviny, pocet primek a bodu.
Veta: Existuje KPR(n) prave kdyz NOLC(n)=n-1.
Veta: Pro n = mocnina prvocisla existuje KPR(n) (dukaz na cviceni).
Prednaska 13.5. (J.Kratochvil):
Model vypoctu Turingovym strojem, deterministicky a nedeterministicky TS,
tridy P a NP, pojem polynomialni prevoditelnosti, NP-uplnost. Cookova veta:
Splitelnost je NP-uplny problem.
Zkousky: Kdo chce prijit na zkousku do 24.5., napiste email na valtr zavinac kam tecka mff atd.
Prednaska 27.2. (Kratochvil):
Mocniny matice sousednosti, kostry pres Laplacian i pres rekurzi.
Prednaska 5.3. (Valtr):
Hladovy algoritmus na minimalni kostru, Boruvkuv algoritmus (naznak).
Tri klasicke algoritmicke problemy o grafech:
problem obchodniho cestujiciho (okruzni jizdy),
problem hamiltonovskych grafu, problem cinskeho postaka (kropiciho vozu).
Algoritmus na nalezeni optimalniho reseni problemu obch. cest. lze pouzit na
vyreseni problemu ham. grafu. 2-aproximace problemu obch. cest. pomoci
algoritmu na nalezeni kostry grafu.
Prednaska 12.3. (Valtr):
Dukaz vety o poctu koster uplneho grafu pomoci multinomickych koeficientu.
Toky v sitich (uvod).
Prednaska 19.3. (Valtr):
Toky v sitich: veta o tocich, Ford-Fulkersonuv algoritmus.
Prednaska 26.3. (Kratochvil):
Definice hranove a vrcholove souvislosti grafu. Vztah mezi nimi.
Ford-Fulkersonova a Mengerova veta.
Prednaska 2.4. (Valtr):
Hallova veta. Definice k-faktoru, 4-pravidelny graf ma 2-faktor, jednodussi implikace v Tuttove vete.
Prednaska 16.4. (Kratochvil):
Tuttova veta. Edmondsuv algoritmus pro hledani nejvetsiho parovani.
Prednaska 23.4. (Kratochvil):
Hamiltonovske kruznice - Chvataluv uzaver. Usate lemma.
Prednaska 30.4. (Valtr):
Vytvorujici funkce: uvod, operace s posloupnostmi,
odvozeni vzorce na vypocet n-teho Fibonacciho cisla.
Prednaska 7.5. (Valtr):
Pokracovani vytvorujicich funkci: binomicka a zobecnena binomicka veta,
pocet binarnich stromu.
Uvodni priklad pro Ramseyovu vetu (z 6 lidi se 3 znaji nebo 3 neznaji).
Prednaska 14.5. (Kratochvil):
Veta o kontrakci v 3-souvislem grafu. Dukaz Kuratowskeho vety.
Plan prednasky 21.5. (Valtr):
Ramseyovy vety.