UIINP14 Graph theory

Faculty of Philosophy and Science in Opava
Winter 2024
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 9:45–11:20 B1
  • Timetable of Seminar Groups:
UIINP14/A: Wed 18:55–20: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, 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
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 2022, Winter 2023.
  • Enrolment Statistics (recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2024/UIINP14