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
ke stazeni zde
3.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).
17.3.2009 (Kratochvil)
Konecne projektivni roviny Definice, rad KPR, konstrukce KPR prvociselneho radu.
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.
24.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.
31.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
7.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 souvislost
5.5.2009 (Kratochvil)
Rovinne grafy
Kresleni grafu do roviny a na povrch sfery, otazka vnejsi steny nakresleni.
"Usate" lemma o vytvareni vrcholove 2-souvislych grafu.
Lemma o vytvareni 3-souvislych grafu (je-li G vrcholove 3-souvisly graf s alespo
n 5 vrcholy, pak existuje hrana, jejiz kontrakce neporusi 3-souvislost).
Lemma o kresleni vrcholove 2-souvislych grafu {v kazdem nakresleni je kazda sten
a 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 p
odle vrcholove souvislosti grafu = 0, 1, 2, a >= 3).
19.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