NMIN331 Základy kombinatoriky a teorie grafů
(P. Valtr)
LS 2016/17


Přednáška: ctvrtek 14:00 K8
Cvičení: po prednasce ve ctvrtek v 15:40 v K8

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: prijmeni zavinac kam.mff.cuni.cz

Probraná témata:

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, rez, minimalni rez, maximalni tok. (Hlavni) Veta o tocich. Ford-Fulkersonuv algoritmus na nalezeni max. toku. Veta o celociselnosti.

System ruznych reprezentantu, Hallova veta (dukaz pomoci toku v sitich).

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. Lemma o usich (= usate lemma).

Rovinne grafy: Definice oblouku, rovinne grafy, rovinne nakresleni grafu, definice steny a topologicke kruznice, Jordanova veta o topologicke kruznici (bez dukazu), K_5 neni rovinny graf. K_3,3 neni rovinny graf, 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). Barveni polit. map a rovinnych grafu, vztah mezi nimi, veta o 4 barvach (bez dukazu, je velmi slozity). Dukazu vety o 5 barvach.

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 horni odhad velikosti Ramseyovych cisel. Shurova veta. 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.

Blokova struktura grafu.

Dukaz Cantorovy-Bernsteinovy vety pres nekonecne grafy.

Nekolik klasickych uloh z kombinatoriky (problem hamiltonovske kruznice, problem obchodniho cestujiciho, problem kropiciho vozu).

Slozitost. Tridy P a NP.