Course detail

Theory of Graphs

FAST-HA53Acad. year: 2024/2025

Various types of graphs and their applications. Basic structures defined for graphs used for their classification. Tractable and intractable combinatorial problems as modelled by graphs. Essential algorithms used to solve graph problems. Theory of NP-completeness.

Language of instruction

Czech

Number of ECTS credits

2

Mode of study

Not applicable.

Guarantor

RNDr. Karel Mikulášek, Ph.D.

Department

Institute of Mathematics and Descriptive Geometry (MAT)

Entry knowledge

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

Rules for evaluation and completion of the course

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

Aims

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.
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.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

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

Recommended literature

Not applicable.

Type of course unit

 

Exercise

26 hod., compulsory

Teacher / Lecturer

RNDr. Karel Mikulášek, Ph.D.

Syllabus

1. Definition of directed and undirected graphs. 2. Special undirected graphs, subgraphs, graph connectivity. 3. Trees. 4. Homomorphisms and isomorphisms of graphs. 5. Digraphs, tournaments. 6. Eulerian graphs, Hamiltonian graphs. 7. Chromatic number of a graph, planar graphs, plane graphs. 8. Spanning tree of a graph, minimum spanning tree problem, Kruskal's algorithm. 9. Dijkstra and Warshall-Floyd algorithms for finding shortest paths in graphs. 10. Flow in a network. Ford Fulkerson algorithm for finding maximum flow. 11. Problems solvable in polynomial time and NP complete problems. 12. Heuristic algorithms, travelling salesman problem. 13. Revision, reserve.