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  kconnectivity of graphs (Menger's theorem), cyclic properties of graphs and applications, 3rd4th 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, 11th12th  introduction to the theory of flows and linear optimization, basic simplex algorithm

Learning activities and teaching methods

Interactive lecture, Taskbased study method, Students' selfstudy
 Contact hours
 52 hours per semester
 Preparation for comprehensive test (1040)
 26 hours per semester
 Preparation for an examination (3060)
 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 
Taskbased study method 
Students' selfstudy 
assessment methods 

Combined exam 
Recommended literature


Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 8070829397.

Demel, Jiří. Grafy a jejich aplikace. 1. vyd. Praha : Academia, 2002. ISBN 8020009906.

Diestel, Reinhard. Graph theory. 3rd ed. Berlin : Springer, 2006. ISBN 3540261834.

Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0849339820.
