Úvod do kombinatoriky a teórie grafov
2023/2024

Cvičenia

Precvičená látka: Matematická indukcia, úplná matematická indukcia
Prednáška: Dirichletov princíp (základná a frekvenčná forma), pravidlo súčtu a súčinu
Odporúčané čítanie: oddiel o matematickej indukcii z knihy Matouška a Nešetřila (v treťom vydaní má číslo 1.3), oddiely o Dirichletovom princípe z Brualdiho knihy (v štvrtom vydaní majú čísla 2.1 a 2.2).

Precvičená látka: Dirichletov princíp (základná a frekvenčná forma), optimalizačné kombinatorikcé úlohy.
Pre ďalšie precvičovanie Dirichletovho princípu odporúčam knižku: Lev Bukovský, Igor Kluvánek: Dirichletov princíp, Škola mladých matematikov. Je v nej veľa úloh, niektoré aj s riešeniami alebo návodmi.
Online prednáška z KMS na tému Dirichletov princíp. Pre tento predmet je relevantná len časť do 1:16:30. Nasledujúce úlohy svojou náročnosťou prekračujú rámec tohto predmetu.
Prednáška: variácie s opakovaním.
odporúčané čítanie: oddiel „four basic counting principles” z brualdiho knihy (v štvrtom vydaní má číslo 3.1).

Precvičená látka: Enumeračné pravidlá
Odporúčané čítanie: súvisiace oddiely z knihy Matouška a Nešetřila (v treťom vydaní majú čísla 3.1, 3.2 a 3.3).
Prednáška: variácie s opakovaním, kombinácie bez opakovania (definícia, počet a zopár vlastností).

Precvičená látka: Štandardné kombinatorické konfigurácie : variácie s opakovaním aj bez, kombinácie bez opakovania, úlohy s kruhom.
Video s niekoľkými vyriešenými úlohami k cvikám.
Prednáška: kombinácie bez opakovania, kombinačné čísla a ich vlastnosti, binomická veta
V skriptách si k tomu prečíajte začiatok sekcie 3.5 Kombinácie bez opakovania (str. 39 – 41).

Precvičená látka: Kombinatorické dôkazy binomických identít.
Prednáška: kombinácie s opakovaním, polynomická veta
V skriptách sekcia 3.6 Kombinácie s opakovaním, permutácia s opakovaním (str. 45 – 47)

Precvičená látka: Počítanie súm
Prednáška: Princíp inklúzie a exklúzie
Videoprednáška (Pokrýva celé skriptá, aj s príkladmi, o trochu viac ako bolo na prezenčnej prednáške.)
Text k prednáške viete nájsť v knihe od Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, sekcia 2.4 (str. 69 – 76).

Precvičená látka: Kombinatorické konfigurácie II
Rozširujúce čítanie pre záujemcov: kapitola o vytvárajúcich (generujúcich) funkciách z knihy Matouška o Nešetřila (v treťom vydaní má číslo 12).
Prednáška: Úvod do teórie grafov

Cvičenia: Dokončenie PIE a Úvod do teórie grafov
Ďalšie úlohy na precvičenie Pre tento kurz sú relevantné len príklady po príklad s číslom 33.
HOLOTŇÁK, Ondrej: Zbierka úloh z teórie grafov (diplomová práca) Obsahuje aj riešenia úloh a definície pojmov. Taktiež pokrýva témy aj nad rámec tohto predmetu.

Miesto prednášky budú cvičenia: Krúžok 1INF2 (s doc. Máčajovou) v F1-326, krúžky 1INF1 a 1INF3 (s Jozefom Rajníkom) v posluchárni B
Pracvičená látka (9:50): Asymptotické odhady
Precvičená látka (riadne cvičenia): Stromy, bipartitné, eulerovské grafy.