## Graph AlgorithmsThe website is continuously updated.
Obsah: ## 2024/2025 -- Tuesday 9:00-11:50, Room L314## The course structureThree-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)
## ProjectThe 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 |