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
Pozadavky ke zkousce
Nasledujici odkazy jsou na ucebnici R. Diestel: Graph Thoery. 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 (tu jsme uz nestihli na prednasce, takze tato konstrukce je ke zkousce nepovinna).
(kapitola 14.1)