Kombinatorika - NMAG403

• Anglický název: Combinatorics
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Garant: prof. RNDr. Jan Kratochvíl, CSc.
• Vyučující: prof. RNDr. Jan Kratochvíl, CSc.; doc. RNDr. Pavel Valtr, Dr.
• Třída: M Mgr. MSTR; M Mgr. MSTR > Povinné
• Kategorizace předmětu: Matematika > Algebra

Anotace

čeština

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)

angličtina

Basic topics of graph theory and regular combinatorial structures.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (01.04.2015)

Podmínky zakončení předmětu

čeština

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)

angličtina

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.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (14.10.2023)

Literatura

čeština

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)

Požadavky ke zkoušce

čeština

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)

angličtina

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.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)

Sylabus

čeština

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)

angličtina

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.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)