Kombinatorika a grafy I - NDMI011

• Anglický název: Combinatorics and Graph Theory I
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2014
• 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í
• Způsob výuky: prezenční
• Garant: RNDr. Ondřej Pangrác, Ph.D.; doc. RNDr. Jiří Fiala, Ph.D.; doc. RNDr. Vít Jelínek, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Neslučitelnost : NDMA001
• Záměnnost : NDMA001
• Je neslučitelnost pro: NDMI031, NDMA001
• Je prerekvizitou pro: NDMI069, NDMI021, NDMI068, NPFL049
• Je záměnnost pro: NDMI031, NDMA001

Anotace

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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.

Literatura

čeština

Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (07.02.2017)

Kučera: Kombinatorické algoritmy

Matoušek, Nešetřil: Kapitoly z diskrétní matematiky

Nešetřil: Teorie grafů

angličtina

Poslední úprava: 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)

Sylabus

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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