UIINP14 Graph theory

Faculty of Philosophy and Science in Opava
Winter 2022
Extent and Intensity
2/2/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Luděk Cienciala, Ph.D. (lecturer)
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 B2
  • Timetable of Seminar Groups:
UIINP14/A: Wed 8:55–10:30 B4, 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 this course students learn the basic concepts of the proving techniques and possible applications of graph theory.
Learning outcomes
Students will be able to: - define important concepts of graph theory. - use graph algorithms. - apply the acquired knowledge on concrete examples.
Syllabus
  • 1. Graphs and simple graphs, vertex degree.
  • 2. Subgraphs, graph representation by matrices, paths, cycles, connected and unconnected graphs.
  • 3. Trees.
  • 4. Special families of graphs - complete graphs, bipartite and multi-partite graphs, isomorphism and automorphism.
  • 5. Matching and covering, edge coloring, matching and covering in bipartite graphs, the algorithm of seeking unsaturated alternating paths.
  • 6. Vertex coloring, planar graphs.
  • 7. The four-colour problem, non-planar graphs, Euler graphs, maze-like tasks - Tarry's algorithm of Trémaux.
  • 8. Hamilton graphs.
  • 9. Directed graphs, tournaments, networks, flows, and cuts.
  • 10.Algorithm to find the minimum spanning tree, Prim's algorithm, Kruskal's algorithm, General scheme of graph search.
  • 11.Bread-First search, Depth-First search, 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
  • 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 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
    not specified
  • ŠEDA, Miloš. Teorie grafů [online]. Brno: VUT, 2003. Dostupné na: http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf. [cit. 8. 10. 2017]
Teaching methods
Interactive lecture
Tutorials
Assessment methods
Credit: Compulsory attendance at seminars min. 75%. A written form of verification of study results.
For the exam, the student can obtain a maximum of 60 points. A minimum of 30 points is required for successful completion.
Language of instruction
Czech
Further Comments
Study Materials
The course can also be completed outside the examination period.
The course is also listed under the following terms Winter 2019, Winter 2020, Winter 2021, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2022, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2022/UIINP14