Elementary Introduction to Graph Theory

Garant předmětu:

Zuzana Masáková

Lecturer:

Petr Ambrož

Tutor:

Petr Ambrož

Supervisor:

Department of Mathematics

Synopsis:

The course provides an explanation of basic graph theory followed by a survey of common graph algorithms.

Requirements:

Syllabus of lectures:

1. Basic and enumerative combinatorics.

2. The Notion of a graph.

3. Trees and spanning trees.

4. Eulerian trails and Hamiltonian cycles.

5. Flows in networks.

6. Colouring and matching.

7. Planar graphs.

Syllabus of tutorials:

Study Objective:

Knowledge:

Basic notions of graph theory.

Skills:

Orienation in elementary graph algorithms and their use for solving practical problems.

Study materials:

Povinná literatura:

[1] J.A. Bondy, U.S.R. Murty: Graph theory. Graduate Texts in Mathematics 244. Springer, New York, (2008).

Doporučená literatura:

[2] M. Bóna. A Walk Through Combinatorics. World Scientific, Singapoore (2006)

[3] Ján Plesník. Grafové algoritmy. Veda, Bratislava, (1983).

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:

• BS Aplikovaná informatika (compulsory course of the specialization)