Předmět Teorie grafů (KIP / QTEGR)
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 KIP / QTEGR - Teorie grafů, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Předmět předpokládá základní znalosti z teorie grafů a rozvíjí je do oblasti pokročilých témat teorie grafů, přesahuje i do dalších disciplín (algebra, kombinatorika) zejména zaměřených na problémy optimalizace systémů. Cílem je získat přehled o typických problémech z teorie grafů a metodách jejich řešeni. Součástí je řešení praktických problémů s využitím teorie grafů, vybrané aplikace a používané algoritmy. Osnova: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, minimální kostra.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, hranové řezy. Věta o maximálním toku a minimálním řezu.
Literatura
Demel, J. Grafy. SNTL Praha, 1988. Demel, Jiří. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.Diestel, R. Graph Theory. Springer-Verlag, 1997. ISBN 0-387-98211-6.Gross, J., Yellen, J. Graph theory and its applications. CRC Press, London, New York, 1998. ISBN 0-8493-3982-0.Bollobás, Béla. Modern graph theory: with 118 figures. New York, 1998. ISBN 0-387-98488-7.Bondy, J.A. Murty U.S.R. Graph Theory. 1st ed. New York, 2008. ISBN 978-1-84628-969-9.&. [1] Jiří Močkoř, Úvod do diskrétní matematiky, Ostravská univerzita 1992, [2] J.Gross, J.Yellen, Graph Theory and its Applications, CRC Press, Londo, New York 1998 [3] Jiří Demel, Grafy, SNTL Praha, 1988 . &, &.
Požadavky
Úspěšné absolvování písemné zkoušky.
Garant
prof. RNDr. Jiří Močkoř, DrSc.
Vyučující
prof. RNDr. Jiří Močkoř, DrSc.