Terminated in academic year 2009/2010
Graph Theory I
| Type of study | Doctoral |
|---|---|
| Language of instruction | Czech |
| Code | 457-0925/01 |
| Abbreviation | TGI |
| Course title | Graph Theory I |
| Credits | 10 |
| Coordinating department | Department of Applied Mathematics |
| Course coordinator | doc. Mgr. Petr Kovář, Ph.D. |
Subject syllabus
Přednášky:
Grafy a jednoduché grafy. Isomorfismus grafů. Incidenční matice a
matice sousednosti. Podgrafy. Stupeň vrcholu. Cesty a cykly.
Stromy, mosty a oddělující množiny(řezy). Artikulace.
Souvislost grafů, bloky.
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. Kuratowského věta, věta o
čtyřech barvách.
Orientované grafy. Orientované cesty, orientované cykly.
Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu.
Eulerovské a Hamiltonovské grafy.
Grafy a jednoduché grafy. Isomorfismus grafů. Incidenční matice a
matice sousednosti. Podgrafy. Stupeň vrcholu. Cesty a cykly.
Stromy, mosty a oddělující množiny(řezy). Artikulace.
Souvislost grafů, bloky.
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. Kuratowského věta, věta o
čtyřech barvách.
Orientované grafy. Orientované cesty, orientované cykly.
Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu.
Eulerovské a Hamiltonovské grafy.