Graph Algorithms

The website is continuously updated.

Obsah:

Additional Resources
Selected students' works
Year 2019/2020
Historie předmětu

2024/2025 -- Tuesday 9:00-11:50, Room L314

The course structure

Three-hour lecture usually consists of lecturing (approx. 2 hours) and demonstrational exercises (approx. 1 hour). Both, by Zbyněk Křivka.

Materials (lecture slides)

Slides with animations (other lectures will be added during the semester) (PDF, version 2024-09-16)
Text generated from slides (suitable for printing) (PDF, version 2019-12-11)
Introduction to Graph Algorithms for Shortest-Paths Problems (PDF) - short educational paper about the basic algorithms to find shortest paths (2017)

Project

The detailed information will be given at the first/second lecture. The students register for the project in StudIS.

Exercises

Exercise 1: Graph Representation
Exercise 2: Breath-First Search
Exercise 3: Depth-First Search
Exercise 4: Topological Order
Exercise 5: Strongly Connected Components
Exercise 6: Minimum Spanning Trees
Exercise 7: Kruskal and Prim algorithm
Exercise 8: Single-source Shortest Paths (Bellman-Ford, DAG, Dijkstra)
Exercise 9: All-pairs Shortest Paths (methods using adjacency-matrix representation)
Exercise 10: Maximum Flow (Ford-Fulkerson method, Maximum matching in bipartite graphs)

Additional Resources

Graph Theory (wikipedia)
Graph Theory (book by Reinhard Diestel)
A polynomial 3-coloring solver with proofs
Algovize (demonstration of algorithms for minimum spanning trees, network flows, shortests paths and some non-graph algorithms such as sorting algorithms); Text for Algovision (EN, too)
Algorithm Animations and Visualizations (the collection of classical graph and non-graph algorithms)
Algorithm Design (slides) (the collection of slides and supporting materials for book J. Kleinberg, É. Tardos: Algorithm Design, Addison-Wesley, 2006)

The selected seminar works and bachelor/master thesis

Demonstration application of selected graph algorithms (Katarína Galanská) - modular Java application with GUI (version 2018-05-28)
Maximal flow/minimum cut in Networks (Benjamin Makovský)

CHANGES LOG

2019/2020: new course, see Czech version of this course

History of this course

2023/2024 -- Monday 11:00-13:50, Room M104

2019/2020 -- Thursday 11:00-13:50, Room E104