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


Přednáška: úterý 10:40 K4
Cvičení: po prednasce v úterý v 12:20 v K2

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: valtr/honza zavinac kam.mff.cuni.cz

Probraná témata:

Prednaska 18.2.
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 (zatim bez dukazu).