|
Lecturer(s)
|
-
Kopal Stanislav, doc. 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 |
|---|
| Knowledge |
|---|
| Knowledge of basic definitions and notations of graph theory in a range of the course KMA/DMA is assumed. |
| formulate basic notions and knowledge of the graph theory, mainly undirected |
| formulate basic algorithms from the filed of unweighted and weighted graphs |
| Skills |
|---|
| define basic notions of the graph theory, mainly undirected |
| apply basic proof techniques in the graph theory |
| use basic matrix calculus in the graph theory |
| Competences |
|---|
| N/A |
| N/A |
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| knowledge of basic notions and theorems of hamiltonian properties of graphs |
| basic knowledge from the field of vertex and edge colouring - Brook's theorem and Heawood's theorem (vertex), Konig's theorem and Vizing's theorem (edge) |
| basic knowledge of the Ramsey theory - formulate problem, Ramsey theorem |
| spectral theory of graphs - basic definitions and knowledge, spectra of basic graph classes |
| formulate linear programming problem, formulate basic variant of the Simplex algorithm |
| Skills |
|---|
| formulate hamiltonian properties |
| formulate basic knowledge from the field of vertex and edge colourings of graphs |
| knowledge of the basics of the Ramsey theory and spectral theory of graphs |
| use of simplex algorithm in the linear programming |
| Competences |
|---|
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Interactive lecture |
| Task-based study method |
| Self-study of literature |
| Skills |
|---|
| Interactive lecture |
| Individual study |
| Task-based study method |
| Competences |
|---|
| Interactive lecture |
| Task-based study method |
| Self-study of literature |
| Individual study |
| assessment methods |
|---|
| Knowledge |
|---|
| Combined exam |
| Written exam |
| Oral exam |
| definitions of notions in a range of the subject KMA/UTG, namely hamiltonian properties of graphs, vertex and edge colourings, Ramsey theory, spectral graph theory and basics of linear programming |
| Skills |
|---|
| Oral exam |
| Written exam |
| Combined exam |
| definitions of notions in a range of the subject KMA/UTG ability to formulate mathematical theorems including sketches of proofs ability to solve simple types of problems using simplex algorithm |
| Competences |
|---|
| Oral exam |
| Written exam |
| 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.
|