Graphs and Algorithms (FSI-SGA-A)

Academic year 2024/2025
Supervisor: prof. RNDr. Josef Šlapal, CSc.  
Supervising institute: ÚM all courses guaranted by this institute
Teaching language: English
Course type: departmental course
Aims of the course unit:

The course aims to acquaint the students with the theory of graphs and graph-based algorithms, which are commonly used to solve problems in engineering and many other areas.

The students will be made familiar with the basics of the theory of graphs and graph algorithms. This will provide them with tools for using graphs to model various practical problems, which may then be solved by using the graph algorithms.
Learning outcomes and competences:
 
Prerequisites:
 
Course contents:

The course will provide students with basic concepts of the theory of graphs and with some algorithms based on that theory. After the basic definitions, the classic problems will be discussed including the Euler path and Hamilton cycle of a graph, vertex colouring, planar graphs etc. The next concept to be investigated will be trees and algorithms for a minimal spaning tree finding. Students will also learn about bipartite graphs, matching problem and shortest path problem. Direcdted graphs will also be discusses including algorithms for critical path finding. Finally, networks and flows in them will be deal with. The course will be oriented towards applications of graphs that can be found in many areas, particularly in technological sciences. Emphasis will be placed on applications in computer science, optimization, theory of control, and operation research.
Teaching methods and criteria:
 
Assesment methods and criteria linked to learning outcomes:

The course unit credit is awarded on condition of having attended the seminars actively and passed a written test. The exam has a written and an oral part. The written part tests student's ability to deal with various problems using the knowledge and skills acquired in the course. In the oral part, the student has ro prove that he or she has mastered the related theory.

 

The attendance at seminars is required and will be checked systematically by the teacher supervising the seminar. If a student misses a seminar, an excused absence can be cpmpensated for via make-up topics of exercises.
Controlled participation in lessons:
 
Type of course unit:
    Lecture  13 × 2 hrs. optionally                  
    Exercise  13 × 1 hrs. compulsory                  
Course curriculum:
    Lecture

  1. Basic con cepts

  2. Walks, paths and, cycles

  3. Trees and spanning trees

  4. Vertex coloring

  5. Planarity

  6. Sorting algorithms

  7. Shortest path problem

  8. Edge colouring

  9. Bipartite graphs

  10. Sorting

  11. Directed graphs

  12. Critical path problem

  13. Flows and Networks
    Exercise Seminars will closely follow the lectures.
Literature - fundamental:
1. Biggs, N.L.: Discrete Mathematics, Oxford Science Publications 1999
3. Zverovich, V.: Modern Applications of Graph Theory, OUP Oxford 2021 
4. Saoub, K.R.: Graph Theory, An Introduction to Proofs, Algorithms, and Applications, Chapman and Hall/CRC 2021
7.

Bondy, J.A., Murty, U.S.R.: Graph Theory, Springer 2008
Literature - recommended:
1. Sedláček, J.: Úvod do teorie grafů, Academia, Praha 1977
2. Willson, J.R., Watkins, J.J.: Graphs: An Introductory Approach, Wiley 1990
3. Wallis, W.D.: A Beginner's Guide to Graph Theory, Birkhäuser Boston 2000
5.  Gross, J.L., Yellen, J., Anderson, M.: Graph Theory and its Applications, Chapman and Hall/CRC, 2023
The study programmes with the given course:
Programme Study form Branch Spec. Final classification   Course-unit credits     Obligation     Level     Year     Semester  
N-MAI-A full-time study --- no specialisation -- Cr,Ex 4 Compulsory 2 1 W
N-MAI-P full-time study --- no specialisation -- Cr,Ex 4 Compulsory 2 1 W
N-AIM-A full-time study --- no specialisation -- Cr,Ex 4 Compulsory 2 2 W
N-LAN-A full-time study --- no specialisation -- Cr,Ex 4 Compulsory 2 1 W
C-AKR-P full-time study CZS -- Cr,Ex 4 Elective 1 1 W