Charles Explorer logo
🇬🇧

Graph Theory

Class at Faculty of Education |
OB2310015

Syllabus

Main topics:

§ Definition of the basic concepts (graph, complete graph, circle, path, tree). The score of a graph.

§ Connected graphs, distance in graphs, closed paths, Hamiltonian circle, Eulerian graphs.

§ Representations of a graph: matrix of neighbourhood, matrix of incidence.

§ Independence of a graph, the theory of coding.

§ Planar graphs, maps, graph colouring, the four colour problem.

Annotation

The aim of the seminar is to make students acquainted with the basic notions and methods of graph theory, such as isomorphism of graphs, different ways of introducing a graph, trees, complete graphs, skeleton, planar graphs, paths in a graph, Euler graphs, hamiltonian graphs, graph coloring, graph algorithms. Recommended literature: Bosák: Grafy a ich aplikácie (Alfa, Bratislava 1980), Sedláček: Úvod do teorie grafů (Academia, Praha 1981), Fuchs: Diskrétní matematika pro učitele (MU Brno, 2001) a Matoušek a Nešetřil: Kapitoly z diskrétní matematiky (UK Praha, 2003).