|
|
|
||
|
The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph
theory.
Last update: T_KAM (20.04.2008)
|
|
||
|
LS 2025/26, English session (Hadi Zamani): To earn credit, a total of 50 points is needed. Up to 30 points can be obtained by active participation in the tutorials (solving the tasks and presenting their solutions). Two quizzes—one mid-semester and one at the end of the semester—are assigned 30 points each. The quiz questions will be selected from the homework assignments.
Tutorial credit is a prerequisite for taking the exam. Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (16.02.2026)
|
|
||
|
R. Diestel: Graph theory, 3rd edition, Springer, 2005.
H. Wilf: Generatingfunctionology (https://www.math.upenn.edu/~wilf/DownldGF.html). Last update: Jelínek Vít, doc. RNDr., Ph.D. (23.06.2016)
|
|
||
|
The exam will be oral, with an opportunity for written preparation. 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. Before taking the exam, a candidate must first get credit from the tutorial. Last update: Jelínek Vít, doc. RNDr., Ph.D. (14.02.2023)
|
|
||
|
Matchings in general graphs. Hamiltonian cycles, Ore condition, Chvátal closure. Surfaces of higher genus, generalized Euler's formula, Heawood's formula. Lemma on the contractible edge, Tutte's theorem on 3-connected graphs, Kuratowski's theorem. Graph coloring, Brooks' theorem, Vizing's theorem. Tutte polynomial: equivalent definitions, important points, cycle space, and cut space of a graph. Ordinary and Exponential Generating Functions. Burnside's lemma, Polya's enumeration, examples of applications. Sunflower theorem, Erdös-Ko-Rado Theorem, Turan's Theorem Perfect graphs, Dilworth's theorem. Chordal graphs. Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (27.09.2020)
|