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


Přednáška: patek 9:00 K5
Cvičení: po prednasce v patek v 10:40 v K5

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 22.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, rez, minimalni rez, maximalni tok. (Hlavni) Veta o tocich - zneni.

Prednaska 1.3.
Dukaz vety o tocich (pricemz dukaz existence maximalniho toku probran na cviceni). Elementarni tok, nasycena cesta, nenasycena (vylepsujici) cesta.