UIINP14 Teorie grafů

Filozoficko-přírodovědecká fakulta v Opavě
zima 2022
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
RNDr. Radka Poláková, Ph.D. (cvičící)
Garance
doc. RNDr. Luděk Cienciala, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Rozvrh
Po 8:05–9:40 B2
  • Rozvrh seminárních/paralelních skupin:
UIINP14/A: St 8:55–10:30 B4, R. Poláková
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
V daném předmětu se studenti seznámí se základními pojmy, s důkazovými technikami a možnými aplikacemi teorie grafů.
Výstupy z učení
Student bude po absolvování předmětu schopen: - definovat důležité pojmy teorie grafů. - používat grafové algoritmy. - aplikovat získané poznatky na konkrétních příkladech.
Osnova
  • 1. Grafy a jednoduché grafy, stupeň vrcholu.
  • 2. Podgrafy, reprezentace grafů pomocí matic, cesty, cykly, dosažitelnost, souvislost, souvislé, nesouvislé grafy, vzdálenost v grafu, excentricita vrcholu, průměr a poloměr grafu.
  • 3. Stromy, třídy grafů.
  • 4. Další třídy grafů - kompletní grafy, bipartitní a multipartitní grafy, izomorfismus, automorfismus. Vrcholová a hranová souvislost, bloky.
  • 5. Párování, pokrytí, hranové barvení grafů, párování a pokrytí v bipartitních grafech, algoritmus hledající nesaturované alternující cesty.
  • 6. Vrcholové barvení grafů, planární grafy.
  • 7. Problém 4 barev, Neplanární grafy, Eulerovské grafy, Úlohy typu bludiště - Tarryho algoritmus, Trémauxův algoritmus.
  • 8. Hamiltonovské grafy, orientované grafy.
  • 9. Orientované grafy, turnaje, sítě, toky a řezy.
  • 10. Algoritmus nalezení minimální kostry grafu, Primův algoritmus, Kruskalův, Obecné schéma prohledávání grafu, značkování vrcholů.
  • 11. Prohledávání grafů do šířky, do hloubky, Backtracking.
Literatura
    povinná literatura
  • Cienciala, L., Ciencialová, L. Teorie grafů a grafové algoritmy. Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-060-3. info
    doporučená literatura
  • Bondy, A., Murty, U. S. R. Graph Theory. Springer, 2011. info
  • Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8. info
  • Merris, R. Graph Theory. New York : John Wiley, 2001. ISBN 0-471-38925-0. info
  • KOVÁŘ, Petr. Úvod do teorie grafů [online]. VŠB TU v Ostravě, 2016. Dostupné na: http://homel.vsb.cz/~kov16/files/uvod_do_teorie_grafu.pdf. [cit. 8. 10. 2017]
  • HLINĚNÝ, Petr. Základy Teorie grafů [online]. Masarykova univerzita. 2010. Dostupné na: https://is.muni.cz/do/1499/el/estud/fi/js10/grafy/Grafy-text10.pdf [cit. 8. 10. 2017]
  • GERA, Ralucca, Craig LARSON a Stephen HEDETNIEMI. Graph theory: Favorite Conjectures and OpenProblems. New York: Springer, 2016. ISBN 978-3-319-31938-4. info
  • KOCAY, William L a Donald L KREHER. Graphs, Algorithms and Optimization. 2nd Edition. Boca Raton,USA: CRC Press, 2016. ISBN 978-1-4822-5116-6. info
  • MILKOVÁ, Eva. Teorie grafů a grafové algoritmy. Hradec Králové: Gaudeamus, 2013. ISBN 978-80-7435-267-6. info
    neurčeno
  • ŠEDA, Miloš. Teorie grafů [online]. Brno: VUT, 2003. Dostupné na: http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf. [cit. 8. 10. 2017]
Výukové metody
Přednáška s aktivizací
Cvičení
Metody hodnocení
Zápočet: Povinná účast na cvičeních min. 75 %. Písemná forma ověření studijních výsledků.
U zkoušky může student získat maximáně 60 bodů. Pro úspěšné ukončení je zapotřebí získat minimálně 30 bodů.
Další komentáře
Studijní materiály
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2019, zima 2020, zima 2021, zima 2023, zima 2024.