UIIABP0021 Teorie grafů

Filozoficko-přírodovědecká fakulta v Opavě
zima 2021
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
doc. RNDr. Luděk Cienciala, Ph.D. (cvičí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 B1
  • Rozvrh seminárních/paralelních skupin:
UIIABP0021/A: Po 9:45–11:20 B2, 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ů.
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
  • 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
  • ŠEDA, Miloš. Teorie grafů [online]. Brno: VUT, 2003. Dostupné na: http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf
  • 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.
  • 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
  • Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8. info
  • BONDY, J a MURTY. Graph theory. New York: Springer, 2010. ISBN 978-1-84996-690-0. info
  • MERRIS, Russell. Graph theory. John Wiley, 2001. ISBN 0-471-38925-0. info
Výukové metody
Přednáška, 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ů.
Předmět je zařazen také v obdobích zima 2020, zima 2022, zima 2023, zima 2024.