Basics of graph theory and systems of sets. Recommended for specialization Mathematical Structures within
General Mathematics and for bachelor's program in Information security.
Last update: G_M (16.05.2012)
Úvodní kurs, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po
strukturální, tak po algoritmické stránce. Doporučeno pro zaměření Matematické struktury na Obecné matematice
a pro obor MMIB.
Last update: G_M (16.05.2012)
Course completion requirements -
The credit for the exercise is given for solving home problems. At least 20 points are required for credit. (Home assignments will be given for at least 40 possible points.) The nature of the conditions does not allow repeated attempts for obtaining the credit. The credit is necessary to register for the exam.
Last update: Fiala Jiří, doc. RNDr., Ph.D. (14.02.2025)
V průběhu semestru bude zadáno několik sérií domácích úloh. Pro zápočet je potřeba získat alespoň 20 bodů (Úlohy budou zadány na alespoň 40 možných bodů.) Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce.
Last update: Fiala Jiří, doc. RNDr., Ph.D. (14.02.2025)
Literature -
Literature according to the recommendation of the teacher.
Last update: Hladík Milan, prof. Mgr., Ph.D. (17.04.2013)
Literatura dle doporučení učitele.
Last update: Hladík Milan, prof. Mgr., Ph.D. (17.04.2013)
Requirements to the exam -
The exam is oral. The knowledge and skills examined correspond to the sylabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the aquired 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 enroling to an exam.
Last update: Kratochvíl Jan, prof. RNDr., CSc. (18.02.2018)
Zkouška je ústní, v nutných případech budu probíhat distančně přes internet. 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.
Last update: Valtr Pavel, doc. RNDr., Dr. (11.02.2023)
Syllabus -
Overview of basics of computational complexity and NP-completeness. Inclusion-exclusion principle and its applications. Generating functions. Finite projective planes, latin squares. Hall theorem and its applications. Flows in digraphs. k-connectivity of graphs. Ramsey theory.
Last update: G_M (16.05.2012)
Základy NP-úplnosti - nedeterministické Turingovy stroje, Cookova věta, základní NP-úplné problémy (3-splnitelnost, Hamiltonovská kružnice, nezávislá množina, exaktní pokrytí).
Odhady faktoriálu a binomických koeficientů.
Princip inkluze a exkluze a jeho aplikace (šatnářka).
Vytvořující funkce a jejich aplikace.
Konečné projektivní roviny, latinské čtverce a jejich ortogononalita.
Hallova věta a aplikace.
Toky v sítích.
k-souvislost grafů, Mengerovy věty pro (ne)orientovane grafy ve verzích pro vrcholy a hrany.
Základni Ramseyovy věty, věta pro p-tice, Schurova věta a další aplikace.
