 | On Saturday 19th October 2024 there will be a shutdown of some components of the information system. Especially the work with files in Thesis modules will be particularly unavailable. Please postpone your requests for a later time. |
|
|
|
||
|
Basic topics of graph theory and regular combinatorial structures.
Last update: Hladík Milan, prof. Mgr., Ph.D. (01.04.2015)
|
|
||
|
Credit for recitations is given after obtaining at least 50% points from home assignments (typically 4 sets of problems per semester) + at least 50% attendance of the recitations. These can be substituted in both ways following the formula 2x+4y>=3, where x is the ratio of attendance and y is the ratio of correctly solved home assignments. There is no alternative way nor second try. Last update: Kratochvíl Jan, prof. RNDr., CSc. (14.10.2023)
|
|
||
|
Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2002
Diestel, R.: Graph Theory, Graduate Texts in Mathematics, Volume 173, Springer Verlag, Fourth Edition 2010
Hall, M. Jr.: Combinatorial Theory, Wiley, New York, 1986
Bollobás, B.: Modern Graph Thoery, Graduate Texts in Mathematics, Springer Verlag, 1998 Last update: T_KA (14.05.2013)
|
|
||
|
The exam is oral and may be performed remotely. The knowledge and skills examined correspond to the syllabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the acquired skills to simple situations related to the topics of the class are subject of the examination. Credit from the recitations must be obtained prior to enrolling to an exam. Last update: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)
|
|
||
|
Basic stracutural and algorithmic topics in graph theory.
Network flows and measures of graph connectivity.
Structural aspects of set systems, systems of distinct representatives, Hall theorem.
Matchings in graphs, Tutte theorem, Edmonds algorithm.
Planar graphs, a proof of Kuratowski theorem.
Hamiltonian cycles in graphs.
Chromatic number and chooseability of graphs, edge-coloring (Vizing theorem), coloring graphs embeddable on surfaces of higher genus.
Regular combinatorial structures, their existence.
Finite projective planes.
Balanced incomplete block designs.
Steiner triple systems.
Symmetric designs, Bruck-Ryser-Chowla theorem.
Hadamard matrices.
Mutually ortogonal Latin squares. Last update: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)
|