Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2019/2020

Introduction to Graph Theory A

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
01ZTGA ZK 4 4+0 Czech
Lecturer:
Petr Ambrož (guarantor)
Tutor:
Supervisor:
Department of Mathematics
Synopsis:

The course provides a coherent explanation of modern graph theory, some applications are discussed.

Requirements:
Syllabus of lectures:

1) Basic notion of graph theory

2) Edge and vertex connectivity (Menger Theorem)

3) Bipartite graphs

4) Trees and forests, cutting edges

5) Spanning trees (Matrix-Tree Theorem)

6) Euler tours and Hamilton cycles

7) Maximal and perfect matching

8) Edge coloring

9) Flows in networks

10) Vertex coloring

11) Plannar graphs (Kuratowski theorem)

12) Spectrum of an adjacency matrix

13) Extremal graph theory

Syllabus of tutorials:
Study Objective:

Knowledge:

Notions of graph theory, their basic properties and mutual relations.

Abilities:

Application of the theory in modelling and solving of particular questions and tasks.

Study materials:

References:

[1] J.A. Bondy, U.S.R. Murty. Graph theory.

Graduate Texts in Mathematics 244. Springer, New York, (2008).

Recommended references:

[2] R. Diestel. Graph theory.

Graduate Texts in Mathematics 173. Springer-Verlag, Berlin, (2005).

[3] L. Lovasz, M.D. Plummer. Matching Theory. North-Holland Publishing Co., Amsterdam, (1986).

Note:
Time-table for winter semester 2019/2020:
Time-table is not available yet
Time-table for summer semester 2019/2020:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2020-06-03
For updated information see http://bilakniha.cvut.cz/en/predmet24524505.html