Course: Fundamentals of Graph Theory

« Back
Course title Fundamentals of Graph Theory
Course code KMA/UTG
Organizational form of instruction Lecture + Tutorial
Level of course Bachelor
Year of study 3
Semester Winter
Number of ECTS credits 5
Language of instruction Czech
Status of course Compulsory, Compulsory-optional, Optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Holub Přemysl, Doc. RNDr. Ph.D.
  • Tomiczková Světlana, RNDr. Ph.D.
Course content
1st week - basic definitions and notations of graph theory, bridges and cut vertices 2nd week - k-connectivity of graphs (Menger's theorem), cyclic properties of graphs and applications, 3rd-4th week - hamiltonian graphs - necessary and satisfactory conditions, 5th week - hamiltonian properties in powers of graphs, 6th week - vector spaces of cycles and edge cuts, 7th week - eigenvalues of graphs and spectrum of graphs, 8th week - vertex colouring of graphs, Brook's theorem, 9th week - edge colouring of graphs, Vizing's theorem, 10th week - introduction to Ramsey theory, 11th-12th - introduction to the theory of flows and linear optimization, basic simplex algorithm

Learning activities and teaching methods
Interactive lecture, Task-based study method, Students' self-study
  • Contact hours - 52 hours per semester
  • Preparation for comprehensive test (10-40) - 26 hours per semester
  • Preparation for an examination (30-60) - 52 hours per semester
prerequisite
professional knowledge
Knowledge of basic definitions and notations of graph theory in a range of the course KMA/DMA is assumed.
learning outcomes
After finishing of this course the student will have basic knowledge of the field of cyclic properties of graphs, vertex and edge colouring of graphs, spectral theory of graphs, Ramsey theory and discrete optimization.
teaching methods
Interactive lecture
Task-based study method
Students' self-study
assessment methods
Combined exam
Recommended literature
  • Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
  • Demel, Jiří. Grafy a jejich aplikace. 1. vyd. Praha : Academia, 2002. ISBN 80-200-0990-6.
  • Diestel, Reinhard. Graph theory. 3rd ed. Berlin : Springer, 2006. ISBN 3-540-26183-4.
  • Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0-8493-3982-0.


Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Applied Sciences General Mathematics (2012) Mathematics courses 3 Winter
Faculty of Applied Sciences Mathematics and its Applications (2017) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics and its Applications (2015) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics for Business Studies (2016) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics for Business Studies (2015) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics and its Applications (2016) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics for Business Studies (2016) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics for Business Studies (2017) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics and its Applications (2016) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics and its Applications (2015) Mathematics courses 2 Winter
Faculty of Applied Sciences General Mathematics (2012) Mathematics courses 3 Winter
Faculty of Applied Sciences Mathematics for Business Studies (2017) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics and its Applications (2017) Mathematics courses 2 Winter
Faculty of Applied Sciences Mathematics for Science (2012) Mathematics courses 3 Winter