The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph
theory.
Last update: T_KAM (10.04.2011)
Přehledová přednáška o klasických výsledcích v kombinatorice a teorii grafů. Předpokládají se znalosti v rozsahu
NDMI011 nebo NDMA001.
Course completion requirements - Czech
Last update: doc. RNDr. Vít Jelínek, Ph.D. (27.09.2018)
Podmínky získání zápočtu na cvičeních V. Jelínka: pro nárok na zápočet je potřeba získat alespoň 25 bodů za řešení domácích úkolů a za aktivní účast na cvičeních. Povaha kontroly předmětu vylučuje opravné termíny u zápočtů.
Podmínkou konání zkoušky je zisk zápočtu.
Literature -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (23.06.2016)
R. Diestel: Graph theory, 3rd edition, Springer, 2005.
H. Wilf: Generatingfunctionology (https://www.math.upenn.edu/~wilf/DownldGF.html).
Last update: PaedDr. Jan Kuchař (04.10.2016)
R. Diestel: Graph theory, 3rd edition, Springer, 2005.
H. Wilf: Generatingfunctionology (https://www.math.upenn.edu/~wilf/DownldGF.html).
The exam has an oral form, with students being given an opportunity for a written preparation before the oral examination itself begins. The topics of the exam correspond to the syllabus of the course, as covered by the lectures and the tutorials. The exam may include combinatorial problems that can be solved by applying or generalizing the results presented at the lectures and tutorials.
Last update: doc. RNDr. Vít Jelínek, Ph.D. (11.10.2017)
Zkouška má ústní formu, s možností písemné přípravy předcházející vlastnímu ústnímu zkoušení. Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních. Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení kombinatorických úloh.
Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
Tutte's and Petersen's theorem
Hamilton cycles, Ore's theorem, Chvátal closure
Surfaces of higher genus, generalized Euler's formula, Heawood's formula
Tutte's theorem on 3-connected graphs, Kuratowski's theorem
Brooks' theorem, Vizing's theorem
Tutte polynomial: equivalent definitions, important points