Course detail
Graph Algorithms
FSI-9GRA Acad. year: 2026/2027 Both semester
Supervisor
Department
Learning outcomes of the course unit
Prerequisites
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
Language of instruction
Czech
Aims
The course aims to acquaint the students with the graph theory and graph-based algorithms that extend the knowledge acquired in subjects courses focused on artificial intelligence, operations research, project management and computer networks and are commonly used to solve problems in engineering and other areas.
The students will be made familiar with the basics of the graph theory and graph algorithms. This will provide them with tools for using graphs to model various practical problems, which may then be solved by using the graph algorithms.
Specification of controlled education, way of implementation and compensation for absences
The study programmes with the given course
Programme D-APM-P: Applied Mathematics, Doctoral
branch ---: , 0 credits, recommended course
Type of course unit
Lecture
20 hours, optionally
Syllabus
1. Definition of a graph and basic terms.
2. Computer representation of a graph.
3. Time and space complexity of algorithms.
4. Graph searching, backtracking, branch and bound method.
5. Applications of path problems, shortest paths, network graphs.
6. Eulerian trails, Hamiltonian paths and circles.
7. Connected components, trees and spanning trees.
8. Steiner trees.
9. Voronoi diagrams, Delaunay triangulation.
10. Graph colouring, cliques.
11.-12. Network flows.
13. Graph matching.