Osnova přednášek
1) Grafy, jednoduché grafy. Podgrafy. Stupeň vrcholu. Incidenční matice a matice sousednosti.
2) Cesty a cykly. Vzdálenost a excentricita.
3) Stromy a kostry, bipartitní grafy.
4) Isomorfismus grafů, automorfismy.
5) Souvislost grafů, mosty, oddělující množiny (řezy), bloky, artikulace.
6) Párování a pokrytí v grafech a bipartitních grafech. Přiřazovací problém. Úplné párování.
7) Hranová barvení a jejich aplikace. Chromatický index grafu. Vizingova věta.
8) Vrcholová barvení a jejich aplikace. Chromatické číslo grafu. Brooksova věta.
9) Planární grafy a jejich aplikace. Eulerův vzorec. Kuratowského věta, věta o čtyřech barvách.
10) Neplanární grafy, míry neplanarity
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, cykly, turnaje.
13) Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.
1) Grafy, jednoduché grafy. Podgrafy. Stupeň vrcholu. Incidenční matice a matice sousednosti.
2) Cesty a cykly. Vzdálenost a excentricita.
3) Stromy a kostry, bipartitní grafy.
4) Isomorfismus grafů, automorfismy.
5) Souvislost grafů, mosty, oddělující množiny (řezy), bloky, artikulace.
6) Párování a pokrytí v grafech a bipartitních grafech. Přiřazovací problém. Úplné párování.
7) Hranová barvení a jejich aplikace. Chromatický index grafu. Vizingova věta.
8) Vrcholová barvení a jejich aplikace. Chromatické číslo grafu. Brooksova věta.
9) Planární grafy a jejich aplikace. Eulerův vzorec. Kuratowského věta, věta o čtyřech barvách.
10) Neplanární grafy, míry neplanarity
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, cykly, turnaje.
13) Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.