Czech

2

Not applicable.

Institute of Mathematics and Descriptive Geometry (MAT)

Students will be acquainted with the basics of the theory of simple graphs, directed graphs, and multigraphs. They will get an understanding of the relationship between the planarity and colourability of a graph. They will be able to apply the basic methods to solving tractable combinatorial problems on graphs as well as the travelling salesman problem as a representative of intractable NP complete problems.

Basics of combinatorics as taught at secondary schools. Symbol processing.

Not applicable.

Not applicable.

Requirements for successful completion of the subject are specified by guarantor’s regulation updated for every academic year.

1. Definition of graphs, digraphs, multigraphs. Examples.
2. Path in a graph, contiguous graphs, component of a graph. Trees.
3. Homomorfism and isomorfism of graphs. Eulerian and Hamiltonian graphs, applications.
4. Colourability of graphs, independence of graphs. Planar graphs, the Kuratowski theorem. Problem of four colours.
5. Essential combinatorial problems. A good characteristic of a problem.
6. Tractable problems on graphs I.
7. Tractable problems on graphs II.
8. Travelling salesman problem, branch and bound method, heuristic methods.
9. NP-complete problems.
10. Revision.

Not applicable.

After the course, students should be acquainted with the basics of the theory of graphs. They should also be able to apply the knowledge acquired when dealing with problems they may come across as engineers or businessmen.

Extent and forms are specified by guarantor’s regulation updated for every academic year.

Not applicable.

Not applicable.

Nešetřil, J.: Teorie grafů. SNTL, 1978.
Gross, Y; Yellen, J: Graph Theory. CRC Press, 1999.

Not applicable.

26 hours, obligation not entered