Description:

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

Contents:

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. Coloring and matching.
7. Planar graphs.

Recommended literature:

Povinná literatura:
[1] J.A. Bondy, U.S.R. Murty: Graph theory. Springer, New York, 2008.
[2] W. Kocay, D. L. Kreher: Graphs, Algorithms, and Optimization (2nd ed.). Chapman and Hall/CRC, 2016.
[3] R. Diestel: Graph Theory (5th ed.), Springer-Verlag Berlin Heidelberg, 2017.

Keywords:

graph, tree, matching, coloring

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar