|
|
|
||
Vytvořující funkce a kombinatorická enumerace. Extremální otázky v grafech a množinových systémech.
Ramseyova teorie. Toky v sítích. Strukturálni otázky množinových systémů, transverzály a systémy různých
reprezentantů. Pravidelné kombinatorické struktury (bloková schémata, Steinerovy systémy trojic, Latinské čtverce,
konečné projektivní roviny). Vnořování grafů na plochy vyšších rodů.
Poslední úprava: T_KA (14.05.2013)
|
|
||
Zápočet se uděluje za získání alespoň 50% bodů za domácí úkoly (zpravidla 4 serie úloh) + alespoň 50% docházky na cvičení, přičemž obojí lze vzájemně částečně nahradit (přesná podmínka je 2x+4y>=3, kde x je podíl docházky na cvičení a y podíl získaných bodů za domácí úkoly). Povaha kontroly studia neumožňuje opakování této kontroly. Poslední úprava: 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 Poslední úprava: T_KA (14.05.2013)
|
|
||
Zkouška je ústní, může mít kontaktní nebo distanční formu. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce. Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)
|
|
||
Základní strukturální a algoritmické otázky teorie gafů.
Toky v sítích a míra souvislosti grafu.
Extremální otázky v grafech a množinových systémech, systémy různých reprezentantů, Hallova věta.
Párování v grafech, Tutteova věta, Edmondsův algoritmus.
Rovinné grafy, důkaz Kuratowského věty.
Hamiltonovské kružnice v grafech.
Barevnost a vybíravost grafů, hranová barevnost (Vizingova věta), barevnost grafů vnořitelných na plochy vyšších rodů.
Pravidelné kombinatorické struktury, jejich existence.
Bloková schémata.
Steinerovy systémy trojic.
Symetrická schémata, věta Bruck-Ryser-Chowla.
Hadamardovy matice.
Navzájem ortogonální Latinské čtverce.
Konečné projektivní roviny. Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)
|