Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025

Graph Theory

Login to KOS for course enrollment Display time-table
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 80-200-0990-6, (in czechh);

Secend edition 2015, ISBN 80-260-7684-1

Note:
Time-table 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
roomTH:B-476

14:00–15:50
(lecture parallel1)
Thákurova 7 (budova FSv)
roomTH:B-476

16:00–17:50
(lecture parallel1
parallel nr.101)

Thákurova 7 (budova FSv)
Tue
Wed
Thu
Fri
Time-table for summer semester 2024/2025:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-11-04
For updated information see http://bilakniha.cvut.cz/en/predmet23648005.html