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
• 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

Annotation

English

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

Last update: T_KAM (20.04.2008)

Czech

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

English

LS 2023/24, English session (Babak Ghanbari): The credit will be awarded based on 2-3 short tests, active participation in the class and the homework solutions.

Tutorial credit is a prerequisite for taking the exam.

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

Czech

Podmínky získání zápočtu: Zápočet bude za zisk alespoň dvou třetin bodů ze standardních úkolů. Body bude možné získat dle uvážení cvičícího i za bonusové úkoly a aktivní účast na cvičeních.

Povaha kontroly předmětu vylučuje opravné termíny u zápočtů.

Zkoušku lze složit i před získáním zápočtu.

Last update: Veselý Pavel, Mgr., Ph.D. (12.02.2023)

Literature

English

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)

Czech

R. Diestel: Graph theory, 3rd edition, Springer, 2005.

H. Wilf: Generatingfunctionology (https://www.math.upenn.edu/~wilf/DownldGF.html).

Videozáznamy přednášek

Last update: Kuchař Jan, PaedDr. (04.10.2016)

Requirements to the exam

English

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)

Czech

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

English

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)

Czech

Párování v obecných grafech.

Hamiltonovské kružnice, Oreho podmínka, Chvátalův uzávěr.

Plochy vyššího rodu, zobecněná Eulerova formule, Heawoodova formule.

Lemma o kontrahovatelné hraně, Tutteho věta o 3-souvislých grafech, Kuratowského věta.

Barevnost grafů, Brooksova věta, Vizingova věta.

Tutteho polynom: různé definice, význačné body, prostor cyklů a řezů grafu.

Obyčejné a exponenciální vytvořující funkce.

Burnsideovo lemma, Pólyova enumerace, příklady aplikací.

Věta o slunečnici, Erdös-Ko-Radoova věta, Turánova věta.

Perfektni grafy, Dilworthova věta.

Chordální grafy.

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