UIMOIBK008 Graph theory

Faculty of Philosophy and Science in Opava
Winter 2023
Extent and Intensity
0/0/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Luděk Cienciala, Ph.D. (lecturer)
Guaranteed by
doc. RNDr. Luděk Cienciala, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
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, degree of vertex.
  • 2. Subgraphs, matrix representation of graphs, paths, cycles, reachability, connectedness, connected, disconnected graphs, distance v graph, vertex eccentricity, diameter and radius of a graph.
  • 3. Trees, classes of graphs.
  • 4. Other classes of graphs - complete graphs, bipartite and multipartite graphs, isomorphism, automorphism. Vertex and edge continuity, blocks.
  • 5. Pairing, covering, edge coloring of graphs, pairing and covering in  bipartite graphs, algorithm finding unsaturated alternate paths.
  • 6. Vertex coloring of graphs, planar graphs.
  • 7.-8. 4-color problem, Non-planar graphs, Eulerian graphs, Maze type problems - Tarry's algorithm, Trémaux algorithm.
  • 9. Hamiltonian graphs, oriented graphs.
  • 10. Oriented graphs, tournaments, networks, flows and cuts.
  • 11.-12. Minimum skeleton graph finding algorithm, Prim's algorithm, Kruskal's algorithm, General graph search scheme, vertex labeling.
  • 13. Graph search in width, in depth, 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 (probably available only in Czech)
Study Materials
Information on the extent and intensity of the course: 12 hod/sem.
The course is also listed under the following terms Winter 2020, Winter 2021, Winter 2022, Winter 2024.
  • Enrolment Statistics (Winter 2023, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2023/UIMOIBK008