SubjectsSubjects(version: 849)
Course, academic year 2019/2020
   Login via CAS
Graph Theory - OB2310255
Title in English: Teorie grafů
Guaranteed by: Katedra matematiky a didaktiky matematiky (41-KMDM)
Faculty: Faculty of Education
Actual: from 2011
Semester: winter
E-Credits: 2
Examination process: winter s.:
Hours per week, examination: winter s.:1/0 C [hours/week]
Capacity: unknown / unknown (100)
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Note: course can be enrolled in outside the study plan
enabled for web enrollment
priority enrollment if the course is part of the study plan
Guarantor: prof. RNDr. Ladislav Kvasz, DSc., Dr.
Class: Matematika 1. cyklus - povinné
Classification: Mathematics > Mathematics, Algebra, Differential Equations, Potential Theory, Didactics of Mathematics, Discrete Mathematics, Math. Econ. and Econometrics, External Subjects, Financial and Insurance Math., Functional Analysis, Geometry, General Subjects, , Real and Complex Analysis, Mathematics General, Mathematical Modeling in Physics, Numerical Analysis, Optimization, Probability and Statistics, Topology and Category
Annotation -
Last update: JANCARIK/PEDF.CUNI.CZ (19.05.2010)
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).
Aim of the course -
Last update: JANCARIK/PEDF.CUNI.CZ (19.05.2010)

The aim of the seminar is to make students of mathematics education acquainted with the basic notions and techniques of graph theory. On some selected themes the specific methods of argumentation and proofs in graph theory will be illustrated. The motivation by practical problems will be put into the foreground and the effectiveness of graph-theoretical methods will be shown.

Literature -
Last update: JANCARIK/PEDF.CUNI.CZ (19.05.2010)

§ Vrba: Grafy - učebnice pro gymnázia se zaměřením na matematiku, SPN 1989

§ Nešetřil: Teorie grafů, SNTL, Praha 1979

§ Matoušek, Nešetřil: Kapitoly z Diskrétní Matematiky, Matfyzpress, Praha, 2000

§ Sedláček: Úvod do teorie grafů Academia, Praha 1981,

§ Fuchs: Diskrétní matematika pro učitele MU Brno, 2001

Teaching methods -
Last update: JANCARIK/PEDF.CUNI.CZ (19.05.2010)

At the seminar we will present standard problems and on the solution of these problems we will illustrate the fundamental notions and methods of graph theory. Thus a rather concrete approach, close to problem solving will be used.

Requirements to the exam - Czech
Last update: ZHOUF/PEDF.CUNI.CZ (09.11.2011)

Účast ve výuce, závěrečný test.

Syllabus -
Last update: JANCARIK/PEDF.CUNI.CZ (19.05.2010)

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.

Charles University | Information system of Charles University |