Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2021/2022

Graph Theory

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
11Y1TG KZ 2 2P+0C Czech
Lecturer:
Lucie Kárná
Tutor:
Lucie Kárná
Supervisor:
Department of Applied Mathematics
Synopsis:

Basic concepts and terminology of graph theory, graph representation. Problems of graph theory, problem instance. Graph search algorithms, trees, minimum spanning tree, shortest path problem, Eulerian path, bipartite graph matching, flow networks, circulations, critical path method, traveling salesman problem. Problem of existence and optimization and algorithms for their solving. Computational complexity, dealing with NP-complete problems, heuristic approach.

Requirements:

Graph theory basics

Syllabus of lectures:
Syllabus of tutorials:
Study Objective:

Deeper understanding of graph theory basics. Learning of bacis concepts and problems in the field of algoritmization. Classical problems of graph theory and algorithms for their solving. Introducing to time complexity and efficiency of algorithms.

Study materials:

Demel, J: Grafy a jejich aplikace, Praha, Academia, 2002

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Praha, Karolinum, 2009

Note:
Time-table for winter semester 2021/2022:
Time-table is not available yet
Time-table for summer semester 2021/2022:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2022-07-04
For updated information see http://bilakniha.cvut.cz/en/predmet24063405.html