Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Graphs and their Applications

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
128GA10 ZK 4 2P English
Garant předmětu:
Lecturer:
Jiří Demel
Tutor:
Supervisor:
Department of Applied Informatics
Synopsis:

Fundamentals of graph theory. Emphasis is laid on basic concepts, applications and algorithms. From the contents: connectivity, strong conectivity, trees, shortest

paths, flows in networks, Eulerian and Hamiltonian

paths, colorings, independent sets, planar graphs.

Requirements:

no prerequisities

Syllabus of lectures:

Basic notions (graphs, vertices, edges, degrees, paths, cycles, etc.).

Applications of path problems.

Searching algorithms (labeling, breath first search, depth first search).

Notions based on undirected paths (connected components, trees, minimal spanning trees).

Notions based on directed paths (strongly connected components, topological sorting, rooted trees, transitive closure).

Shortest path.

Problems related to shortest paths.

Flows in networks.

Application of network flow problems.

Matchings, Assignment problem.

Eulerian graphs, Chinese postman problem.

Hamiltonian paths and cycles. Travelling salesman problem.

Colorings, independent sets and cliques.

Planar graphs.

Syllabus of tutorials:

Basic notions (graphs, vertices, edges, degrees, paths, cycles, etc.).

Applications of path problems.

Searching algorithms (labeling, breath first search, depth first search).

Notions based on undirected paths (connected components, trees, minimal spanning trees).

Notions based on directed paths (strongly connected components, topological sorting, rooted trees, transitive closure).

Shortest path.

Problems related to shortest paths.

Flows in networks.

Application of network flow problems.

Matchings, Assignment problem.

Eulerian graphs, Chinese postman problem.

Hamiltonian paths and cycles. Travelling salesman problem.

Colorings, independent sets and 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:

Diestel, R.: Graph Theory, Springer, 1996,

Swamy, M., N., S., Thulasiraman, K., Graphs, Networks and Algorithms. New York, John Wiley&Sons, Inc., 1981.

Demel, J.: Graphs and their Applications, (internal material).

Note:
Time-table for winter semester 2023/2024:
Time-table is not available yet
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-03-27
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet24412905.html