UIINK14 Graph theory

Faculty of Philosophy and Science in Opava
Winter 2024
Extent and Intensity
12/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 offered to students of any study field.
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.
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
The course can also be completed outside the examination period.
Information on the extent and intensity of the course: Přednáška 12 HOD/SEM.
The course is also listed under the following terms Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023.
  • Enrolment Statistics (recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2024/UIINK14