Course detail

Graph Theory

FSI-VTGAcad. year: 2017/2018

The course provides an introduction to graph theory and familiarises students with basic terms.
It deals with the following topics: Graph representation. Time complexity of algorithms.
Data structures (binary heap, disjoint sets, ...). Eulearian trails, Hamiltonian paths.
Breadth-first searching, depth-first searching, backtracking, branch and bound method.
Connectivity and reachability. Shortest path problems (Dijkstra's algorithm, Floyd-Warshall algorithm). Network graphs. Trees, spanning tree problem, Steiner tree problems.
Fundamentals of computational geometry, Voronoi diagrams, Delaunay triangulation.
Network flows. Graph colouring. Graph matching.

Learning outcomes of the course unit

The students will be made familiar with the basics of the graph theory and graph algorithms. It will provide them with tools for using graphs to model various practical problems, which may then be solved by using the graph algorithms.


Successful completion of the course "Graph Theory" is conditional on basic knowledge of set theory, combinatorics and operations research.


Not applicable.

Recommended optional programme components

Not applicable.

Recommended or required reading

Chartrand, G. and Oellermann, O.R. : Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
Demel, J.: Grafy a jejich aplikace. ACADEMIA, Praha, 2002.
Kolář, J.: Theoretical Computer Science. ČVUT FEL, Praha, 1998.
Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001.
Chartrand, G. and Oellermann, O.R. : Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004.
Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998.
Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.
Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002.

Planned learning activities and teaching methods

The course is taught through lectures explaining the basic principles and theory of the discipline. Exercises are focused on practical topics presented in lectures.

Assesment methods and criteria linked to learning outcomes

The course-unit credit is awarded on condition of having implemented a nontrivial graph algorithm in a programming language (e. g. C++, Java, Python, etc.) The exam has a written form and tests students’ knowledge of terms and fundamental algorithms.

Language of instruction


Work placements

Not applicable.


The course aims to acquaint the students with the graph theory and graph-based algorithms that extend the knowledge acquired in courses focused on artificial intelligence, operations research, project management and computer networks and are commonly used to solve problems in engineering and other areas.

Specification of controlled education, way of implementation and compensation for absences

Since the attendance at seminars is required, it will be checked systematically by the teacher supervising the seminar. If a student misses a seminar, an excused absence can be compensated for via make-up topics of exercises.

Classification of course in study plans

  • Programme M2I-P Master's

    branch M-AIŘ , 2. year of study, winter semester, 5 credits, compulsory
    branch M-AIŘ , 2. year of study, winter semester, 5 credits, compulsory

Type of course unit



26 hours, optionally

Teacher / Lecturer


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.

Computer-assisted exercise

26 hours, compulsory

Teacher / Lecturer


Seminars will focus on a computer implementation of graph algorithms and searching and testing WEB software based on the graph theory.