UIIABP0021 Graph Theory

Faculty of Philosophy and Science in Opava
Winter 2021
Extent and Intensity
2/2/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Luděk Cienciala, Ph.D. (lecturer)
doc. RNDr. Luděk Cienciala, Ph.D. (seminar tutor)
RNDr. Radka Poláková, Ph.D. (seminar tutor)
Guaranteed by
doc. RNDr. Luděk Cienciala, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable
Mon 8:05–9:40 B1
  • Timetable of Seminar Groups:
UIIABP0021/A: Mon 9:45–11:20 B2, R. Poláková
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives (in Czech)
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ů.
Syllabus (in Czech)
  • 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.
Literature
    required literature
  • Cienciala, L., Ciencialová, L. Teorie grafů a grafové algoritmy. Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-060-3. info
    recommended literature
  • 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 and Stephen HEDETNIEMI. Graph theory: Favorite Conjectures and OpenProblems. New York: Springer, 2016. ISBN 978-3-319-31938-4. info
  • KOCAY, William L and 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 and 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
Teaching methods
Lecture, tutorial
Assessment methods (in Czech)
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ů.
Language of instruction
Czech
The course is also listed under the following terms Winter 2020, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2021, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2021/UIIABP0021