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


Přednáška: streda 9:00 K4

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

Dosud probraná témata:

Prednaska 16.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). Hlavni veta o tocich, priprava jejiho dukazu: rez, kapacita rezu, tvrzeni oznacovana ve skriptech jako Vlastnosti 1-3.