Course detail

Graph Algorithms

FSI-9GRAAcad. year: 2023/2024

The course focuses on graph theory and familiarises students with fundamental terms and algorithms. 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 - visibility graphs, Voronoi diagrams, Delaunay triangulation. Network flows. Graph colouring. Graph matching.

Language of instruction

Czech

Mode of study

Not applicable.

Guarantor

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Department

Institute of Automation and Computer Science (ÚAI)

Entry knowledge

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

Rules for evaluation and completion of the course

The course-unit credit is awarded on condition of having described or implemented a nontrivial graph algorithm. The exam has a written form and tests students’ knowledge of terms and fundamental algorithms.

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.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001. (EN)
Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998. (EN)
Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004. (EN)
Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993. (EN)

Recommended reading

Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp. (EN)
Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991. (EN)
Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002. (EN)

Classification of course in study plans

  • Programme D-APM-P Doctoral 1 year of study, summer semester, recommended course
  • Programme D-APM-K Doctoral 1 year of study, summer semester, recommended course

Type of course unit

 

Lecture

20 hod., optionally

Teacher / Lecturer

prof. RNDr. Ing. Miloš Šeda, Ph.D.

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.