Přeskočit na hlavní obsah
Přeskočit hlavičku
Terminated in academic year 2009/2010

Teorie grafů

Typ studia magisterskénavazující magisterské
Jazyk výuky čeština
Kód 457-0305/02
Zkratka TG
Název předmětu česky Teorie grafů
Název předmětu anglicky Graph Theory
Kreditů 6
Garantující katedra Katedra aplikované matematiky
Garant předmětu doc. Mgr. Petr Kovář, Ph.D.

Subject syllabus

Přednášky:

1) Grafy a jednoduché grafy. Isomorfismus grafů. Incidenční matice a matice sousednosti. Podgrafy. Stupeň vrcholu. Cesty a cykly.
2) 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í.
3) Hranové barvení. Chromatický index grafu. Vizingova věta.
4) Vrcholové barvení. Chromatické číslo grafu. Brooksova věta.
5) Rovinné grafy. Duální graf. Eulerův vzorec pro souvislé planární grafy. Kuratowského věta, věta o čtyřech barvách.
6) Eulerovské a hamiltonovské grafy.
7) Orientované grafy. Orientované cesty, orientované cykly.
8) Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu.



Cvičení:

1) Grafy a jednoduché grafy. Podgrafy. Stupeň vrcholu. Cesty a cykly. Významné třídy grafů.
2) Stromy, mosty a oddělující množiny (řezy). Artikulace.
3) Souvislost grafů.
4) Párování a pokrytí v grafech a biparitních grafech. Perfektní párování.
5) Hranové barvení. Chromatický index grafu.
6) Vrcholové barvení. Chromatické číslo grafu.
7) Rovinné grafy. Eulerův vzorec pro libovolné planární grafy.
8) Eulerovské a hamiltonovské grafy.
9) Orientované grafy. Orientované cesty, orientované cykly.

Literature

D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999).
J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2000).

Advised literature

D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001).