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....
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.