**
NMAG403 Kombinatorika ** - pondeli 15:40 v K12

First exam is on Thursday Dec 19 at 2 p.m. in S10. Topics examined are below.

References for graph theory are to the textbook *R. Diestel: Graph Thoery*, most topics can also be found in Czech in skripticka Tomase Vally .

Network flows. (Chapter 6.2)

Systems of distinct representatives and Hall theorem. (Thm 2.1.2)

Matchings in general graphs, Tutte theorem. (Thm 2.2.1)

Edmonds algorithm for maximum matching. (http://en.wikipedia.org/wiki/Blossom_algorithm)

Vertex- and edge-connectivity of graphs. (Chapters 3.1, 3.2, 3.3)

Planar graphs, Kuratowski theorem (Chapter 4.4)

Hamiltonian cycles in graphs (Chapter 10.1), Smith theorem on Ham cycles in cubic graphs (*A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs (Advances in Graph Theory, Cambridge Combinatorics Conference, Trinity College. Cambridge, 1977,) Ann. Discrete Math. 3 (1978) 259-268*).

References for combiatorial structures are from
*Marshall Hall: Combinatorial Theory, Wiley 1986*.

Latin squares, finite projective planes and orthogonal arrays.
(Chapters 13.1, 12.3, 13.2)

Construction of 2 orthogonal Latin squares of order 12t+10.
(Chapter 13.3 - Thm 13.3.1)

Block designs BIBD(v,k,lambda). Relations among the parameters,
Fisher inequality.
(Chapters 10.1., 10.2)

Symmetric designs. Bruck-Ryser-Chowla theorem.
(Chapter 10.3)

Steiner triple systems. Algebraic formulation. Construction for all
v=1,3 mod 6.
(Chapter 15.4) Construction by Bose and Skolem can be found in *Lindner, C.C.; Rodger, C.A. (1997), Design Theory, Boca Raton: CRC Press*.

Hadamard matrices.
(Chapter 14.1)

The topic covered in the class in January is Hamiltonicity of the block intersection graph of any BIBD, see * A.A. Abueida and D.A. Pike. Cycle extensions in BIBD block-intersection graphs, Journal of Combinatorial Designs 21 (2013) 303-310. *

NDMI037 Geometricke reprezentace grafu I - utery 14:00 v S11

poslední aktualizace 9.10. 2019

© m@f# for contents, RooT for design