Combinatorics and Graph Theory I - NDMI011

• Title: Kombinatorika a grafy I
• Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2016 to 2016
• Semester: summer
• E-Credits: 5
• 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, English
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: doc. RNDr. Martin Tancer, Ph.D.; doc. RNDr. Jiří Fiala, Ph.D.
• Class: Informatika Bc.
• Classification: Informatics > Discrete Mathematics
• Incompatibility : NDMA001
• Is incompatible with: NDMI031
• Is pre-requisite for: NDMI069, NDMI068, NDMI021, NPFL049
• Is interchangeable with: NDMA001, NDMI031

Annotation

English

Last update: PANGRAC/MFF.CUNI.CZ (08.04.2010)

Inclusion-exclusion principle and its applications. Generating functions. Finite projective planes, latin squares. Hall theorem and its applications. Flows in digraphs. k-connectivity of graphs. Ramsey theory.

Czech

Last update: T_KAM (06.05.2001)

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.

Literature

English

Last update: doc. RNDr. Vít Jelínek, Ph.D. (22.11.2012)

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)

R. Diestel: Graph Theory (4th edition), Springer (2010)

Czech

Last update: doc. RNDr. Jiří Fiala, Ph.D. (26.09.2023)

• Kučera: Kombinatorické algoritmy
• Matoušek, Nešetřil: Kapitoly z diskrétní matematiky
• Nešetřil: Teorie grafů
• Videozáznamy přednášek

Syllabus

English

Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

Basic course of the computer science study plan. It extends Discrete Mathematics course and covers fundamentals of graph theory and combinatorics from

both structural and algorithmic point of view.

Estimates on the factorial function and binomial coefficients

The number of spanning trees of the complete graph

Generating functions and applications

Finite projective planes, Latin squares and their orthogonality

Double counting - number of spanning trees of K_n-e, Sperner's theorem on independent systems

Flows in networks

Hall's theorem and its applications, maximum matching in bipartite graphs

Higher connectivity of graphs, Menger-type theorems, structure of 2-connected graphs

Ramsey theory

Czech

Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

• 1 Odhady faktoriálu a binomických koecientů

• 1 Počet koster úplneho grafu (nedeterminantový důkaz).

• 1.5 Vytvořující funkce (chápané jako Taylorovy řady), aplikace

• 1.5 Konečné projektivní roviny, latinské čtverce, jejich ortogonalita.

• 1 Dvojí počítání - počet koster Kn-e, Spernerova věta

• 1 Toky v sítích (minimaxová věta).

• 1 Hallova věta a aplikace (Birkhoff-von Neumannova věta, doplňování latinských čtvercù). Maximální párování v bipartitním grafu.

• 1 k-souvislost, Mengerovy věty pro (ne)orientované grafy ve verzích pro vrcholy a hrany.

• 0.5 Ušaté lemma, struktura 2-souvislých grafù.

• 1.5 Základní Ramseyovy věty, Ramsey pro p-tice, Schurova věta.

• 2 Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód. Existence asymptoticky dobrých kódù (Gilbert-Varshamov). Hammingův a Elias-Bassalygův dolní odhad.

Rozšiřující témata: Steinerovy systémy trojic. Maximální počet hran grafu bez K4 a bez K3.