Základní kurs oboru oboru informatika, 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.
Poslední úprava: Maxová Jana, RNDr., Ph.D. (04.11.2026)
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.
Poslední úprava: Maxová Jana, RNDr., Ph.D. (04.11.2026)
Podmínky zakončení předmětu -
Zápočet bude udělen za aktivní účast na cvičeních (přesný rozsah a konkrétní interpretaci aktivní účasti stanoví cvičící příslušného kroužku). Až dvě chybějící účasti je možné nahradit vyřešením zadaných domácích úkolů, jejichž řešení student osobně odprezentuje cvičícímu. V odůvodněných případech (zejména kombinované studium) je možné touto formou nahradit i více účastí. Zápočet je nutnou podmínkou účasti u zkoušky, přednášející může stanovit výjimku pro předtermíny.
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Passing grade for tutorials (zápočet) is obtained on the basis active participation in the seminars (the specific definition and quantification of “active participation” is determined by the instructor of the respective seminar). Up to two absences may be made up by completing assigned homework, the solutions to which the student must personally present to the instructor. In justified cases (particularly for combined form students), it is possible to make up even more absences in this manner. Obtaining the credit is a prerequisite for taking the exam; exceptions (early exam dates) can be specified by the lecturer.
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Literatura -
J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)
R. Diestel: Graph Theory (4th edition), Springer (2010)
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení -
Forma zkoušky je kombinovaná: písemná a ústní. Požadavky na znalosti u zkoušky odpovídají sylabu předmětu.
Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení úloh.
Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (06.09.2023)
The exam has a combined form: written and oral. The content of the exam corresponds to the syllabus of the course, as covered at the lectures. The students must also demonstrate the ability to apply (and generalize) the results from the lecture in solving combinatorial exercises.
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Sylabus -
Vytvořující funkce. Použití v enumerativní kombinatorice a při řešení rekurencí, počítání binárních stromů, Catalanova čísla.
Asymptotické odhady v kombinatorice. Elementární analytické metody, odhady faktoriálu a koeficientů vytvořujících funkcí, entropické odhady.
Dvojí počítání a extremální kombinatorika. Kombinatorické identity a odhady, maximální počet hran grafů bez trojúhelníků a čtyřcyklů a další příklady.
Náhodné grafy a pravděpodobnostní metoda. Základní modely náhodných grafů a jejich vlastnosti, modelování reálných sítí.
Existenční důkazy pravděpodobnostní metodou, Ramseyova věta a odhady Ramseyových čísel.
Souvislost grafů. Hranová a vrcholová souvislost, Mengerova věta a její vztah k tokům v sítích.
Expandery a separátory. Expanze grafů a její souvislost s náhodnými grafy a s vlastními čísly matice sousednosti.
Párování v grafech. Párování největší velikosti v bipartitních grafech, stabilní párování.
Informační entropie a samoopravné kódy. Entropie a komprese dat, základní parametry samoopravných kódů, detekce a oprava chyb, kombinatorické meze pro parametry kódů, vybrané konstrukce (Hammingovy, Hadamardovy a Reedovy–Solomonovy kódy).
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Generating functions. Applications to enumerative combinatorics and recurrence relations, counting binary trees, Catalan numbers.
Asymptotic estimates in combinatorics. Elementary analytic methods, estimates for factorials and coefficients of generating functions, entropy-based estimates.
Double counting and extremal combinatorics. Combinatorial identities and bounds, the maximum number of edges in triangle-free and four-cycle-free graphs, and further examples.
Random graphs and the probabilistic method. Basic random graph models and their properties, modelling real-world networks.
Existence proofs using the probabilistic method, Ramsey's theorem, and bounds on Ramsey numbers.
Graph connectivity. Edge and vertex connectivity, Menger's theorem and its relationship to network flows.
Expanders and separators. Graph expansion and its connection to random graphs and to the eigenvalues of the adjacency matrix.
Matchings in graphs. Maximum-cardinality matchings in bipartite graphs, stable matchings.
Information entropy and error-correcting codes. Entropy and data compression, basic parameters of error-correcting codes, error detection and correction, combinatorial bounds on code parameters, selected constructions (Hamming, Hadamard and Reed–Solomon codes).
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Výsledky učení -
Po absolvování předmětu student/studentka:
Sestaví vytvořující funkci pro jednoduchý kombinatorický problém, využije ji k řešení rekurence nebo enumerativní úlohy a odhadne růst vybraných kombinatorických posloupností.
Použije metodu dvojího počítání k odvození kombinatorických identit a jednoduchých extremálních odhadů, například pro maximální počet hran grafů s určitými zakázanými podgrafy.
V modelu náhodného grafu (G(n,p)) vypočte očekávaný počet vybraných podgrafů a na příkladech vysvětlí, jak se různé modely náhodných grafů liší svými vlastnostmi a možnostmi využití.
Vysvětlí tvrzení konečné Ramseyovy věty a použije pravděpodobnostní metodu k jednoduchému existenčnímu důkazu, například při odvozování dolních odhadů Ramseyových čísel.
Rozliší hranovou a vrcholovou souvislost grafu a použije Mengerovu a Hallovu větu při řešení jednoduchých úloh o disjunktních cestách, separátorech a párováních. Vysvětlí jejich souvislost s toky v sítích a rozliší úlohy hledání párování největší velikosti a stabilního párování.
Vysvětlí pojem expanze grafu a její důsledky pro existenci malých vyvážených separátorů a vztah s lineárně-algebraickými vlastnostmi matice souvislosti.
Vysvětlí vztah mezi informační entropií a možnostmi bezeztrátové komprese dat a na jednoduchém příkladu odhadne průměrnou délku prefixového kódu.
Z minimální Hammingovy vzdálenosti kódu určí jeho schopnost detekovat a opravovat chyby a pomocí základních kombinatorických mezí odhadne možné parametry samoopravných kódů.
Vysvětlí principy lineárních kódů a na příkladu vybrané algebraické konstrukce ukáže, jak lze vytvořit kód s požadovanou minimální vzdáleností. Porovná existenční výsledky s konkrétními konstrukcemi a vysvětlí význam efektivního kódování a dekódování.
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Upon successful completion of the course, students will be able to:
Construct a generating function for a simple combinatorial problem, use it to solve a recurrence relation or an enumeration problem, and estimate the growth of selected combinatorial sequences.
Use double counting to derive a combinatorial identity or a simple extremal bound, for example a bound on the maximum number of edges in graphs excluding certain subgraphs.
Compute the expected number of copies of a specified graph in the random graph model G(n,p), and explain, using examples, how different random graph models differ in their properties and applications.
Explain the statement of the finite Ramsey theorem and use the probabilistic method to prove a simple existence result, for example to derive a lower bound on Ramsey numbers.
Distinguish edge and vertex connectivity and apply Menger's and Hall's theorems to simple problems involving disjoint paths, separators and matchings. Explain their relationship to network flows and distinguish maximum-cardinality and stable matching problems.
Explain graph expansion and how it constrains the existence of small balanced separators and relates to linear-algebraic properties of the adjacency matrix.
Explain the relationship between information entropy and the limits of lossless data compression, and estimate the average codeword length of a prefix-free code in a simple example.
Given the minimum Hamming distance of a code, determine its error-detection and error-correction capabilities, and use basic combinatorial bounds to estimate feasible code parameters.
Explain the basic principles of linear codes and demonstrate, using a selected algebraic construction, how to obtain a code with a desired minimum distance. Compare existence results with concrete constructions and explain the importance of efficient encoding and decoding.
Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)