Teorie grafů

Přednášky a cvičení:
- Grafy a jednoduché grafy. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu.
- Cesty a cykly v grafu. Excentricita, průměr a poloměr
- Stromy, mosty a bipartitní grafy.
- Isomorfismus grafů
- Vrcholová a hranová souvislost grafů, bloky. Artikulace. Oddělující množiny (řezy).
- Párování a pokrytí v grafech a biparitních grafech. Perfektní párování.
- Hranové barvení. Chromatický index grafu. Vizingova věta.
- Vrcholové barvení. Chromatické číslo grafu. Brooksova věta.
- Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách.
- Nerovinné grafy, míry neplanarity.
- Eulerovské a hamiltonovské grafy.
- Orientované grafy. Orientované cesty, orientované cykly.
- Turnaje a grafové modely