Course details

Graph Algorithms (in English)

GALe Acad. year 2020/2021 Winter semester 5 credits

Current academic year

This course discusses graph representations and graphs algorithms for searching (depth-first search, breadth-first search), topological sorting, searching of graph components and strongly connected components, trees and minimal spanning trees, single-source and all-pairs shortest paths, maximal flows and minimal cuts, maximal bipartite matching, Euler graphs, and graph coloring. The principles and complexities of all presented algorithms are discussed.

Guarantor

Meduna Alexandr, prof. RNDr., CSc. (DIFS)

Course coordinator

Křivka Zbyněk, Ing., Ph.D. (DIFS)

Language of instruction

English

Completion

Examination (written)

Time span

  • 39 hrs lectures
  • 13 hrs projects

Assessment points

  • 60 pts final exam
  • 15 pts mid-term test
  • 25 pts projects

Department

Department of Information Systems (UIFS)

Lecturer

Křivka Zbyněk, Ing., Ph.D. (DIFS)

Instructor

Genčúrová Ľubica, Ing.

Course Web Pages

Public course webpage

Subject specific learning outcomes and competences

Fundamental ability to construct an algorithm for a graph problem and to analyze its time and space complexity.

Learning objectives

Introduction to graph theory with focus on graph representations, graph algorithms and their complexities.

Prerequisite knowledge and skills

Foundations in discrete mathematics and algorithmic thinking.

Study literature

  • Copy of lectures.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (http://www.introductiontoalgorithms.com), McGraw-Hill, 2002.
  • A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
  • J. Demel, Grafy a jejich aplikace, Academia, 2002. (More about the book (http://kix.fsv.cvut.cz/~demel/grafy/))
  • R. Diestel, Graph Theory, Third Edition (http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/), Springer-Verlag, Heidelberg, 2000.
  • J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
  • J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008.
  • J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005.
  • J.L. Gross, J. Yellen: Handbook of Graph Theory (Discrete Mathematics and Its Applications), CRC Press, 2003.

Syllabus of lectures

  1. Introduction, algorithmic complexity, basic notions and graph representations.
  2. Graph searching, depth-first search, breadth-first search.
  3. Topological sort, acyclic graphs.
  4. Graph components, strongly connected components, examples.
  5. Trees, minimal spanning trees, algorithms of Jarník and Borůvka.
  6. Growing a minimal spanning tree, algorithms of Kruskal and Prim.
  7. Single-source shortest paths, Bellman-Ford algorithm, shortest path in DAGs.
  8. Dijkstra algorithm. All-pairs shortest paths.
  9. Shortest paths and matrix multiplication, Floyd-Warshall algorithm.
  10. Flows and cuts in networks, maximal flow, minimal cut, Ford-Fulkerson algorithm.
  11. Matching in bipartite graphs, maximal matching.
  12. Graph coloring.
  13. Eulerian graphs and tours, Hamiltonian graphs and cycles.

Syllabus - others, projects and individual work of students

  1. Solving of selected graph problems and presentation of solutions (principle, complexity, implementation, optimization).

Progress assessment

A mid-term exam evaluation (max. 15 points) and an evaluation of projects (max. 25 points).

Controlled instruction

A written mid-term exam, an evaluation of projects, and a final exam. The minimal number of points which can be obtained from the final exam is 25. Otherwise, no points from the final exam will be assigned to a student.

Course inclusion in study plans

Back to top