Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Combinatorics and Graph Theory 2 - NDMX012

Title:	Kombinatorika a grafy 2
Guaranteed by:	Student Affairs Department (32-STUD)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2020
Semester:	summer
E-Credits:	6
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech
Teaching methods:	full-time
Is provided by:	NDMI012

Guarantor:	prof. Mgr. Zdeněk Dvořák, Ph.D. doc. RNDr. Vít Jelínek, Ph.D.
Class:	Informatika Bc.
Classification:	Informatics > Discrete Mathematics
Pre-requisite :	{NXXX014, NXXX015, NXXX016, NXXX017, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
Incompatibility :	NDMI012
Interchangeability :	NDMI012
Is incompatible with:	NDMI012
Is interchangeable with:	NDMI012

Opinion survey results Examination dates SS schedule Noticeboard

Annotation -

The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph theory.

Last update: T_KAM (20.04.2008)

Course completion requirements -

LS 2024/25, English session (Hadi Zamani): To earn credit, a total of 100 points is needed. The points include ten homework assignments (100 points) and two tests (60 points). Additional 40 points can be obtained based on a self-study and presentation of an assigned topics.

Tutorial credit is a prerequisite for taking the exam.

Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (20.02.2025)

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)

Requirements to the exam -

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)

Syllabus -

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)