GAL Acad. year 2019/2020 Winter semester 5 credits
Language of instruction
Tomko Martin, Ing. (FIT BUT)
Course Web Pages
Subject specific learning outcomes and competences
Why is the course taught
Prerequisite kwnowledge and skills
- Copy of lectures.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 3rd Edition, 1312 p., 2009.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
- J. Demel, Grafy, SNTL Praha, 1988.
- J. Demel, Grafy a jejich aplikace, Academia, 2002. (More about the book)
- R. Diestel, Graph Theory, Third Edition, 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
- Introduction, algorithmic complexity, basic notions and graph representations.
- Graph searching, depth-first search, breadth-first search.
- Topological sort, acyclic graphs.
- Graph components, strongly connected components, examples.
- Trees, minimal spanning trees, algorithms of Jarník and Borůvka.
- Growing a minimal spanning tree, algorithms of Kruskal and Prim.
- Single-source shortest paths, the Bellman-Ford algorithm, shortest path in DAGs.
- Dijkstra's algorithm. All-pairs shortest paths.
- Shortest paths and matrix multiplication, the Floyd-Warshall algorithm.
- Flows and cuts in networks, maximal flow, minimal cut, the Ford-Fulkerson algorithm.
- Matching in bipartite graphs, maximal matching.
- Graph coloring, Chromatic polynomial.
- Eulerian graphs and tours, Chinese postman problem, and Hamiltonian cycles.
Syllabus - others, projects and individual work of students
- Solving of selected graph problems and presentation of solutions (principle, complexity, implementation, optimization).
- Mid-term written examination (15 point)
- Evaluated project(s) (25 points)
- Final written examination (60 points)
- The minimal number of points which can be obtained from the final exam is 25. Otherwise, no points will be assigned to a student.
- The student can ask the responsible teacher to extend the time for the project assignment.
- If a student cannot attend the mid-term exam, (s)he can ask to derive points from the evaluation of his/her first attempt of the final exam.
Course inclusion in study plans
- Programme IT-MSC-2, field MBI, MBS, MGM, MIN, MIS, MMI, MPV, any year of study, Elective
- Programme IT-MSC-2, field MMM, any year of study, Compulsory
- Programme IT-MSC-2, field MSK, 1st year of study, Compulsory
- Programme MITAI, specialisation NADE, NBIO, NCPS, NEMB, NGRI, NHPC, NIDE, NISD, NISY, NMAL, NSEC, NSEN, NSPE, NVER, NVIZ, any year of study, Elective
- Programme MITAI, specialisation NMAT, NNET, any year of study, Compulsory