Kombinatorika a grafy 2 - NDMI012

• Anglický název: Combinatorics and Graph Theory 2
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.; doc. RNDr. Vít Jelínek, Ph.D.
• Vyučující: prof. Mgr. Zdeněk Dvořák, Ph.D.; doc. Mgr. Jan Hubička, Ph.D.; Bc. Josef Tkadlec, Ph.D.; Hadi Zamani, M.Sc.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Neslučitelnost : NDMX012
• Záměnnost : NDMX012
• Je neslučitelnost pro: NDMA002, NDMI032, NDMX012
• Je záměnnost pro: NDMI032, NDMX012, NDMA002

Anotace

čeština

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.

Poslední úprava: T_KAM (10.04.2011)

angličtina

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

Poslední úprava: T_KAM (20.04.2008)

Podmínky zakončení předmětu

čeština

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.

Poslední úprava: Veselý Pavel, Mgr., Ph.D. (12.02.2023)

angličtina

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.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (20.02.2025)

Literatura

čeština

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

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

Videozáznamy přednášek

Poslední úprava: Kuchař Jan, PaedDr. (04.10.2016)

angličtina

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

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

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (23.06.2016)

Požadavky ke zkoušce

čeština

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.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (11.10.2017)

angličtina

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.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (14.02.2023)

Sylabus

čeština

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.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (27.09.2020)

angličtina

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.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (27.09.2020)