Graph Theory
Code  Completion  Credits  Range  Language 

128TG  Z,ZK  4  2P+2C  Czech 
 Course guarantor:
 Jiří Demel
 Lecturer:
 Jiří Demel
 Tutor:
 Jiří Demel
 Supervisor:
 Department of Applied Informatics
 Synopsis:

Graph theory  basic elements, graph tasks formulations, basic algorithms with recognition of calculation efficiency. Connectivity, strong connectivity, trees, spanning trees, flows in networks, matchings, eulerian trails, hamiltonian paths, independent sets, cliques, coloring, plannar graphs.
 Requirements:

No
 Syllabus of lectures:

basliclic terminology
graph modelling of real world problems
Search algorithms,
connectivity and strong connectivity,
acyclic graphs, topological sort,
trees and spanning trees,
shortest paths
flows in networks,
matching, assignment problem
hamiltonian problems
coloring, independent sets, cliques
planar graphs
 Syllabus of tutorials:

basliclic terminology
graph modelling of real world problems
Search algorithms,
connectivity and strong connectivity,
acyclic graphs, topological sort,
trees and spanning trees,
shortest paths
flows in networks,
matching, assignment problem
hamiltonian problems
coloring, independent sets, cliques
planar graphs
 Study Objective:

Ability to use the graph as means of expression to model real situations, ability to solve basic graph problems.
 Study materials:

Demel, J.: Grafy a jejich aplikace, 2002, Academia Praha, ISBN 8020009906, (in czechh);
Secend edition 2015, ISBN 8026076841
 Note:
 Timetable for winter semester 2024/2025:

06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Wed Thu Fri  Timetable for summer semester 2024/2025:
 Timetable is not available yet
 The course is a part of the following study plans:

 Geodézie a kartografie, specializace Geomatika (compulsory elective course)