|
Lecturer(s)
|
-
Masopust Tomáš, doc. RNDr. Ph.D., DSc.
|
|
Course content
|
Syllabus of lectures: 1. Introduction, algorithmic complexity, basic notions and graph reprezentations 2. Graph searching, depth-first search, breadth-first search 3. Topological sorting, acyclic graphs 4. Graph components, strongly connected components 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, the Bellman-Ford algorithm, shortest path in DAGs 8. Dijkstra's algorithm. All-pairs shortest paths 9. Shortest paths and matrix multiplication, the Floyd-Warshall algorithm 10. Flows and cuts in networks, maximal flow, minimal cut, the Ford-Fulkerson algorithm 11. Matching in bipartite graphs, maximal matching 12. Euler graphs and tours and Hamilton cycles 13. Graph coloring
|
|
Learning activities and teaching methods
|
|
Lecture, Demonstration
|
|
Learning outcomes
|
Students will acquire the basic knowledge of graphs and graph algorithms and their complexity analysis.
Learning outcomes and competencies: Ability to construct an algorithm for a graph problem and to analyze its time and space complexity.
|
|
Prerequisites
|
Basic knowledge of discrete mathematics and the ability of algorithmic thinking.
|
|
Assessment methods and criteria
|
Oral exam, Written exam, Seminar Work
Active participation in the class. Completion of assigned homeworks. Passing the final exam.
|
|
Recommended literature
|
-
J. Demel. (2002). Grafy a jejich aplikace. Academia.
-
J. Demel. (1988). Grafy. SNTL Praha.
-
J.A. Bondy, U.S.R. Murty. (2008). Graph Theory. Springer.
-
J.A. McHugh. (1990). Algorithmic Graph Theory. Prentice-Hall.
-
J.L. Gross, J. Yellen. (2005). Graph Theory and Its Applications. Chapman & Hall/CRC.
-
R. Diestel. (2017). Graph Theory. Springer-Verlag, Heidelberg.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest. (2002). Introduction to Algorithms. McGraw-Hill.
|