Předmět Teorie grafů (M5140)
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 M5140 - Teorie grafů, Přírodovědecká fakulta, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Tento kurz je úvodem do teorie grafů. Po absolvování tohoto kurzu budou studenti schopni: používat základní pojmy teorie grafů; definovat a chápat základní vlastnosti grafů, zejména hranovou a vrcholovou souvislost, rovinnost a chromatické číslo; formulovat a aplikovat nejdůležitější výsledky teorie grafů; řešit jednoduché grafové úlohy pomocí standardních efektivních algoritmů.
Osnova
Základní pojmy: definice grafu, základní grafy, reprezentace grafů, izomorfismus grafů, podgrafy, skóre.Sledy, tahy, cesty: nejkratší cesty, počet sledů, markovské řetězce.Toky v sítích: věta o maximálním toku.Hranová a vrcholová souvislost: komponenty, mosty, Mengerova věta, 2-souvislé grafy, bloky grafu, 3-souvislé grafy.Procházení grafu: eulerovské a hamiltonovské grafy, problém obchodního cestujícího.Párování: bipartitní párování, Tutteho věta.Stromy: charakterizace stromů, střed stromu, počet stromů, minimální kostry.Obarvování hran: bipartitní grafy, Vizingova věta, Ramseyho věta.Obarvování vrcholů: Brooksova věta, chromatický polynom.Rovinné grafy: Eulerův vztah, platónská tělesa, Kuratowského věta, Fáryho věta, duální graf, maximální počet hran, věta o čtyřech barvách, rod grafu.Minory: věta Robertsona a Seymoura.Orientace grafů: Robbinsova věta, turnaje.
Literatura
NEŠETŘIL, Jaroslav. Kombinatorika. I, Grafy. 1. vyd. Praha: Státní pedagogické nakladatelství, 1983. 173 s. infoNEŠETŘIL, Jaroslav. Teorie grafů [Nešetřil, 1979]. 1. vyd. Praha: SNTL - Nakladatelství technické literatury, 1979. 316 s. infoPLESNÍK, Ján. Grafové algoritmy. 1. vyd. Bratislava: Veda, 1983. 343 s. infoKUČERA, Luděk. Kombinatorické algoritmy. 2. vyd. Praha: Státní nakladatelství technické literatury, 1989. 286 s. infoWILSON, Robin J. Introduction to graph theory. 4th ed. Harlow: Prentice Hall, 1996. viii, 171. ISBN 0-582-24993-7. infoGraph theory. Edited by Reinhard Diestel. 3rd ed. Berlin: Springer, 2006. xvi, 410s. ISBN 3540261834. info
Požadavky
! M5145 Teorie grafů && !( FI:MA010 Graph Theory )
Garant
doc. Mgr. Michal Kunc, Ph.D.
Vyučující
doc. Mgr. Michal Kunc, Ph.D.Mgr. Eva Vodrážková