The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph
theory.
Last update: T_KAM (20.04.2008)
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.
Last update: T_KAM (10.04.2011)
Course completion requirements - Czech
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.
Last update: Jelínek Vít, doc. RNDr., Ph.D. (27.09.2018)
Literature -
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)
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: Penev Irena, Ph.D. (14.02.2022)
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.
Last update: Jelínek Vít, doc. RNDr., Ph.D. (11.10.2017)
Syllabus -
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
