NMAG403 Kombinatorika - 2017/18

Tuesday 17:20 - K12

Recitations led by Peter Korcsok korcsok@kam.mff.cuni.cz.

Literature:
R. Diestel: Graph Thoery, available on-line on flooved.
T. Valla: Skripticka z kombinatoriky
M. Hall: Combinatorial Theory, Wiley 1986

OCT 3, 2017
Recollection of basic notions from Graph Theory
Graph (directed, undirected, weighted), paths, cycles, connectedness of graphs, trees.
Network flows
Definition of network with edge capacities, flow, and the weight of a flow. Cuts and elementary cuts.
Every cut contains an elementary cut.
For a flow f and a subset A of vertices containing the source and not containing the sink, w(f) = f(A,V-A) - f(V-A,A).
Main theorem: The maximum weight of a flow equals the minimum capacity of a cut. Proof of the "does not exceed" part.


Pozadavky ke zkousce

Nasledujici odkazy jsou na ucebnici R. Diestel: Graph Thoery, available on-line on flooved. Vetsinu grafovych veci lze nalezt v skriptickach Tomase Vally .

Systemy ruznych reprezentantu a Hallova veta. (Veta 2.1.2)
Parovani v obecnych grafech, Tutteova veta. (Veta 2.2.1)
Edmondsuv algoritmus na hledani nejvetsiho parovani v obecnych grafech. (http://en.wikipedia.org/wiki/Blossom_algorithm)
Vrcholova a hranova souvislost grafu. (Kapitoly 3.1, 3.2, 3.3)
Hranova barevnost, Vizingova veta. (Veta 5.3.2)
Vrcholova barevnost grafu vnoritelnych na plochy vyssiho rodu. Heawoodova veta. (http://en.wikipedia.org/wiki/Heawood_conjecture)
Vybiravost grafu. (Kapitola 5.4, zvlaste veta 5.4.2, Lemma 5.4.3, Veta 5.4.4.)
Rovinne grafy, Kuratowskeho veta (Kapitola 4.4)

Nasledujici odkazy jsou na Marshall Hall: Combinatorial Theory, Wiley 1986

Latinské čtverce, konečné projektivní roviny a ortogonální tabulky. (kapitola 13.1, 12.3, 13.2)
Konstrukce 2 navzájem ortogonálních čtverců řádu 12t+10. (kapitola 13.3 - veta 13.3.1)
Bloková schémata BIBD(v,b,r,k,lambda). Základní vztahy mezi parametry. Fisherova nerovnost. (kapitola 10.1., 10.2)
Symetrická schémata (tj. v=b), algebraický popis. Bruck-Ryser-Chowlova věta. (kapitola 10.3)
Steinerovy systémy trojic. Algebraická formulace. Konstrukce STS pro všechny v=1,3 mod 6. (kapitola 15.4) My jsme si ale ukazovali konstrukce podle Bose, Skolem, ktere lze nalezt napr. v Lindner, C.C.; Rodger, C.A. (1997), Design Theory, Boca Raton: CRC Press.
Hadamardovy matice, Paleyova konstrukce. (kapitola 14.1)