Ukončeno v akademickém roce 2009/2010

Teorie grafů I

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

Osnova předmětu

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.

Povinná literatura

J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2003), ISBN 80-246-0084-6.
D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999) .
D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), -2.
P. Kovář, Teorie grafů, pracovní text on-line (2010).

Doporučená literatura

Bondy, U.S.R. Murty: Graph Theory with Applications, American Esevier Publishing Co., New York, 1976, .
Behzad, G. Chartrand, L. Lesniak-Foster: Graphs and Digraphs, Prindle, Weber and Schmid, Boston, 197, .

zpět na vyhledávání