Předmět Teorie grafů I (TGI)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu TGI - Teorie grafů I, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).

Materiál	Typ	Datum	Počet stažení

Cíl

Student by měl- analyzovat reálný problém- přeformulovet jej do řeči teorie grafů- vyřešit příslušný problém užitím příslušných postupů teorie grafů- interpretovat teoretické výsledky v kontextu původní úlohySoučasně je nutno kriticky zhodnotit meze použitelnosti ideálního řešení v reálné situaci.

Osnova

Osnova přednášek 1) Grafy, jednoduché grafy. Podgrafy. Stupeň vrcholu. Incidenční matice a matice sousednosti. 2) Cesty a cykly. Vzdálenost a excentricita.3) Stromy a kostry, bipartitní grafy.4) Isomorfismus grafů, automorfismy.5) Souvislost grafů, mosty, oddělující množiny (řezy), bloky, artikulace.6) Párování a pokrytí v grafech a bipartitních grafech. Přiřazovací problém. Úplné párování. 7) Hranová barvení a jejich aplikace. Chromatický index grafu. Vizingova věta. 8) Vrcholová barvení a jejich aplikace. Chromatické číslo grafu. Brooksova věta. 9) Planární grafy a jejich aplikace. Eulerův vzorec. Kuratowského věta, věta o čtyřech barvách. 10) Eulerovské a hamiltonovské grafy. 11) Orientované grafy. Orientované cesty, cykly, turnaje.12) Toky v sítích, řezy. Věta o maximálním toku a minimálním řezu.V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.

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) ISBN 80-7248-044-8 .D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-0144400-2.P. Kovář, Teorie grafů, pracovní text on-line (2010).

Požadavky

Žádné

Garant

doc. Mgr. Petr Kovář, Ph.D.

Vyučující

doc. Mgr. Petr Kovář, Ph.D.