Přednášky:
1) Grafy a jednoduché grafy. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu.
2) Cesty a cykly v grafu. Excentricita, průměr a poloměr
3) Stromy, mosty a bipartitní grafy.
4) Isomorfismus grafů
5) Vrcholová a hranová souvislost grafů, bloky. Artikulace. Oddělující množiny (řezy).
6) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování.
7) Hranové barvení. Chromatický index grafu. Vizingova věta.
8) Vrcholové barvení. Chromatické číslo grafu. Brooksova věta.
9) Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách.
10) Nerovinné grafy, míry neplanarity.
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, orientované cykly.
13 a 14) Další témata: toky v sítích, řezy. Modely.
Cvičení:
1) Grafy a jednoduché grafy. Podgrafy. Stupeň vrcholu.
2) Cesty a cykly. Významné třídy grafů. Excentricita vrcholů.
3) Stromy, mosty. Bipartitní grafy a Hallova věta
4) Isomorfismus a automorfismus grafů.
5) Vrcholová a hranová souvislost grafů, oddělující množiny (řezy). Artikulace.
6) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. Vztah mezi párováním a pokrytím.
7) Hranová barvení grafů. Chromatický index grafu. Třídy grafů I a II.
8) Vrcholová barvení grafů. Chromatické číslo grafu. Odhady chromatického čísla.
9) Rovinné grafy. Eulerův vzorec pro libovolné planární grafy.
10) Nerovinné grafy a míry neplanarity.
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, orientované cykly.
13 a 14) Další témata: grafové modely a jejich využití.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty dle pokynů přednášejícího. Témata jsou volena z okruhů probíraných na přednášce a jsou uvedena na stránce vyučujícího nebo v elektronickém informačním sytému, například:
1) rovinné grafy a jejich využití při řešení praktické úlohy
2) barvení grafů a jejich využití při řešení praktické úlohy
Pro udělení zápočtu je nutné uznání projektu za alespoň 10 bodů.
1) Grafy a jednoduché grafy. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu.
2) Cesty a cykly v grafu. Excentricita, průměr a poloměr
3) Stromy, mosty a bipartitní grafy.
4) Isomorfismus grafů
5) Vrcholová a hranová souvislost grafů, bloky. Artikulace. Oddělující množiny (řezy).
6) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování.
7) Hranové barvení. Chromatický index grafu. Vizingova věta.
8) Vrcholové barvení. Chromatické číslo grafu. Brooksova věta.
9) Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách.
10) Nerovinné grafy, míry neplanarity.
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, orientované cykly.
13 a 14) Další témata: toky v sítích, řezy. Modely.
Cvičení:
1) Grafy a jednoduché grafy. Podgrafy. Stupeň vrcholu.
2) Cesty a cykly. Významné třídy grafů. Excentricita vrcholů.
3) Stromy, mosty. Bipartitní grafy a Hallova věta
4) Isomorfismus a automorfismus grafů.
5) Vrcholová a hranová souvislost grafů, oddělující množiny (řezy). Artikulace.
6) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování. Vztah mezi párováním a pokrytím.
7) Hranová barvení grafů. Chromatický index grafu. Třídy grafů I a II.
8) Vrcholová barvení grafů. Chromatické číslo grafu. Odhady chromatického čísla.
9) Rovinné grafy. Eulerův vzorec pro libovolné planární grafy.
10) Nerovinné grafy a míry neplanarity.
11) Eulerovské a hamiltonovské grafy.
12) Orientované grafy. Orientované cesty, orientované cykly.
13 a 14) Další témata: grafové modely a jejich využití.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty dle pokynů přednášejícího. Témata jsou volena z okruhů probíraných na přednášce a jsou uvedena na stránce vyučujícího nebo v elektronickém informačním sytému, například:
1) rovinné grafy a jejich využití při řešení praktické úlohy
2) barvení grafů a jejich využití při řešení praktické úlohy
Pro udělení zápočtu je nutné uznání projektu za alespoň 10 bodů.