NMIN331 Základy kombinatoriky a teorie grafů
(P. Valtr, J. Kratochvil)
LS 2025/26


Zkouska: U zkousky bude zkousena latka probrana na prednasce (viz konec tento stranky) plus latka o rozsahu max. 1 prednasky (jeste bude upresneno). Eventualne se muzete naucit podle latky prednesene loni (moznost urcena zejmena pro ty, kdo na prednasku nechodili a naucili se uz lonska temata).

Terminy zkousek: V prvnich dvou tydnech zkouskoveho obdobi (25.5.-5.6.) jsou zatim moje casove moznosti nejiste a budou pravdepodobne dosti omezene. Spise si zkousku planujte predtim nebo potom.
V SIS vypsan termin v patek 15.5. Predbezne uvazuji vypsat dalsi termin zkousky 21./22.5., max 1 termin v obdobi 25.5.-5.6., dale 8./9.6., cca. 16.6., 22.6.

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
M. Mareš, T. Valla: Průvodce labyrintem algoritmů. ke stazeni zde

Email: valtr zavinac kam.mff....

Probraná témata v minulem roce :

Opakovani pojmu z DM: graf, vrchol, hrana, stupen vrcholu, podgraf, indukovany podgraf, tvrzeni: pocet indukovanych podgrafu je 2^|V|, uplny graf, kruznice, cesta (delka kruznice, cesty), cesta v grafu, tah, sled, izomorfismus grafu, priklad: K_4 obsahuje 7 ruznych kruznic, souvisly graf, nesouvisly graf, komponenta, strom, kostra

Toky v sitich: sit, tok, velikost toku, maximalni tok. Tvrzeni: existuje tok max. velikosti (naucte se na zkousku dukaz, ackoliv na prednasce nebyl). Hlavni veta o tocich. Ford-Fulkersonuv algoritmus na nalezeni max. toku. Veta o celociselnosti.

Souvislost grafu: Vrcholovy a hranovy rez, vrcholova a hranova souvislost. Po odebranim hrany nebo vrcholu hranova i vrcholova souvislost zustane zachovana nebo klesne o 1. Vrcholova souvislost je mensi nebo rovna hranove souvislosti (pro libovolny graf). Ford-Fulkersonova veta. Mengerova veta.

System ruznych reprezentantu, Hallova veta.

Ramseyovy vety: 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). Exponencialni dolni i horni odhad velikosti Ramseyovych cisel. Ramseyova veta pro barveni p-tic (bez dukazu).

Vytvorujici funkce: uvod, operace s posloupnostmi. Odvozeni vzorce na vypocet n-teho Fibonacciho cisla. Binomicka a zobecnena binomicka veta, pocet binarnich stromu.

Hamiltonovske grafy, Chvataluv uzaver.

Slozitost. Tridy P a NP.

Dukaz Cantorovy-Bernsteinovy vety pres nekonecne grafy.

Do 30.3. bylo odpredneseno (prednasel P. Valtr):

Opakovani pojmu z DM: graf, vrchol, hrana, stupen vrcholu, podgraf, indukovany podgraf, tvrzeni: pocet indukovanych podgrafu je 2^|V|, uplny graf, kruznice, cesta (delka kruznice, cesty), cesta v grafu, tah, sled, izomorfismus grafu, priklad: K_4 obsahuje 7 ruznych kruznic, souvisly graf, nesouvisly graf, komponenta, strom, kostra

Toky v sitich: sit, tok, velikost toku, maximalni tok. Tvrzeni: existuje tok max. velikosti (naucte se na zkousku dukaz, ackoliv na prednasce nebyl). Hlavni veta o tocich. Ford-Fulkersonuv algoritmus na nalezeni max. toku. Veta o celociselnosti.

Souvislost grafu: Vrcholovy a hranovy rez, vrcholova a hranova souvislost. Po odebranim hrany nebo vrcholu hranova i vrcholova souvislost zustane zachovana nebo klesne o 1. Vrcholova souvislost je mensi nebo rovna hranove souvislosti (pro libovolny graf). Ford-Fulkersonova veta (priprava). Mengerova veta (priprava).

Od 13.4. bylo odpredneseno:

13.4. - Vytvorujici funkce - komb. aplikace mnohoclenu, rozsireni na nekon. rady, Fibonacciho cisla, pocet binarnich stromu (prednasel P. Patak); na zkousku se naucte z Kapitol z DM podkapitolu Rozsireni na nekonecne rady a aspon jednu ze dvou nasledujicich podkapitol (Fib. cisla, resp. binarni stromy)
20.4 - Hallova veta o SRR, Fordova-Fulkersonova veta (prednasel J. Kratochvil, podle skripticek T. Vally a J. Matouska)
27.4. - Mengerova veta, zaklady Ramseyovy teorie, prednasel J, Kratochvil, podle skripticek T. Vally a J. Matouska)
4.5. - Erdosova-Szekeresova veta (podle skripticek T. Vally a J. Matouska), ortogonalni Latinske ctverce a konecne projektivni roviny; prednasel J. Kratochvil
11.5. - Hamiltonovske grafy, Chvataluv uzaver, veta o Chvatalove uzaveru, Diracova veta, 2-aproximacni algoritmus pro problem obchodniho cestujiciho; prednasel P. Valtr
18.5. - Rozhodovaci problemy a prevody (strany 465-471 plus prvni odstavecek na strane 472 online knizky Mares, Valla: Pruvodce labyrintem algoritmu, verze s opravenymi erraty)