#
FI:MA015 Graph Algorithms - Course Information

## MA015 Graph Algorithms

**Faculty of Informatics**

Autumn 2005

**Extent and Intensity**- 2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
**Teacher(s)**- doc. RNDr. Libor Polák, CSc. (lecturer)

doc. RNDr. Jiří Kaďourek, CSc. (seminar tutor)

prof. RNDr. Luboš Brim, CSc. (assistant) **Guaranteed by**- doc. RNDr. Libor Polák, CSc.

Departments - Faculty of Science

Contact Person: doc. RNDr. Libor Polák, CSc. **Timetable**- Mon 14:00–15:50 D2
- Timetable of Seminar Groups:

*L. Polák*

MA015/03: Fri 10:00–10:50 B007,*J. Kaďourek*

MA015/04: Fri 11:00–11:50 B007,*J. Kaďourek* **Prerequisites**-
**M005**Foundations of mathematics ||**MB005**Foundations of mathematics ||(**MB101**Mathematics I &&**MB102**Mathematics II )

Ability of communication about basic mathematical objects and algorithms. **Course Enrolment Limitations**- The course is also offered to the students of the fields other than those the course is directly associated with.
**Fields of study the course is directly associated with**- there are 6 fields of study the course is directly associated with, display
**Course objectives**- Basic graph algorithms are presented: searches, algorithms for minimal spanning trees, various algorithms for shortest paths and flows in nets.In all cases we prove the correctness and estimate the complexity.
**Syllabus**- Elementary graph algorithms (representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components).
- Minimum spanning trees (growing a minimum spanning tree, the algorithms of Kruskal and Prim).
- Single-source shortest paths (shortest paths and relaxation, Dijkstra's algorithm, the Bellman--Ford algorithm, single--source shortest paths in directed acyclic graphs).
- All-pairs shortest paths (shortest paths and matrix multiplication, the Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs).
- Maximum flow (flow networks, the Ford-Fulkerson method, maximum bipartite matching).
- Data structures for graph algorithms (binary heaps, priority queues, data structures for disjoint sets).

**Literature**- CORMEN, Thomas H., Charles E. LEISERSON and Ronald L. RIVEST.
*Introduction to algorithms*. Cambridge: MIT Press, 1990. xi, 1028. ISBN 0262031418. info

- CORMEN, Thomas H., Charles E. LEISERSON and Ronald L. RIVEST.
**Assessment methods**(in Czech)- Standardní přednáška. Ve cvičení studenti referují řešení předem zadaných úloh. Zkouška je písemná.
**Language of instruction**- Czech
**Further Comments**- The course is taught annually.
**Teacher's information**- http://www.math.muni.cz/~polak/grafy.html

- Enrolment Statistics (Autumn 2005, recent)
- Permalink: https://is.muni.cz/course/fi/autumn2005/MA015