Úvod do kombinatoriky a teórie grafov
2025/2026
Cvičenia
V materiáloch k cvičeniam sú zvyčajne niektoré úlohy označené šípkou. Ide o výber dôležitých úloh, ktoré sa prevažne budú riešiť na cvičeniach. Pokiaľ sa nejaké nestihnú, tak je odporúčané, aby ste si ich vyriešili doma.
Týždeň č. 1 (16. 2. – 20. 2. 2026)
- Precvičená látka: Matematická indukcia, úplná matematická indukcia
- Prednáška: Prirodzené čísla a matematická indukcia
- 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
Týždeň č. 2 (23. 2. – 27. 2. 2026)
- Precvičená látka: Dirichletov princíp (základná a frekvenčná forma), optimalizačné kombinatorické ú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: Pravidlo súčtu a súčinu, Dirichletov princíp Dirichletovom princípe z Brualdiho knihy (v štvrtom vydaní majú čísla 2.1 a 2.2).
Týždeň č. 3 (2. 3. – 6. 3. 2026)
- 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, variácie bez opakovania.
- Materiál Kombinatorika cez programovanie vysvetľujúci princípy riešenia kombinatorických úloh pomocou programovania.
Týždeň č. 4 (9. 3. – 13. 3. 2026)
- Precvičená látka: Štandardné kombinatorické konfigurácie : variácie s opakovaním aj bez, kombinácie bez opakovania, úlohy s kruhom.
- Cvičenia pre pokročilých: rekurzívne riešenie kombinatorických úloh.
- Video s niekoľkými vyriešenými úlohami k cvikám.
- Prednáška: permutácie, kombinácie bez opakovania, kombinačné čísla a ich vlastnosti
- V skriptách si k tomu prečítajte začiatok sekcie 3.5 Kombinácie bez opakovania (str. 39 – 41).
Týždeň č. 5 (16. 3. – 20. 3. 2026)
- Precvičená látka: Kombinatorické dôkazy identít a sumy.
- Prednáška: Binomická a polynomická veta, kombinácie s opakovaním, permutácie s opakovaním.
- V skriptách sekcia 3.6 Kombinácie s opakovaním, permutácia s opakovaním (str. 45 – 47)
Týždeň č. 6 (23. 3. – 27. 3. 2026)
- Precvičená látka: Základné kombinatorické konfigurácie II
- Prednáška: Princíp zapojenia a vypojenia
- Videoprednáška (Pokrýva celé skriptá, aj s príkladmi, o trochu viac ako bolo na prezenčnej prednáške.)
Týždeň č. 7 (30. 3. – 3. 4. 2026)
- Piatkové cvičenia odpadli.
- Prednáška: Asymptotické odhady
- Videoprednáška
Týždeň č. 8 (6. 4. – 10. 4. 2026)
- Cvičenia: Princíp inklúzie a exklúzie
- Prednáška: opakovanie pred písomkou
Týždeň č. 9 (13. 4. – 17. 4. 2026)
- Cvičenia: Asymptotické odhady
- Prednáška: Odpadla (ŠVK)
Týždeň č. 10 (20. 4. – 24. 4. 2026)
- Precvičená látka: Teória grafov – základné pojmy.
- Prednáška: Úvod do teórie grafov
Týždeň č. 11 (27. 4. – 1. 5. 2026)
- Cvičenia v piatok odpadli.
- Prednáška: stromy, biaprtitné grafy
Týždeň č. 12 (4. 5. – 8. 5. 2026)
- Precvičená látka: dokončenie minulej sady a stromy
- Prednáška: eulerovské grafy, súvislosť
- Náhrada za piatkové cvičenia je v stredu 8:10. Okrem cvičení v M-IX budú aj cvičenia s doc. Máčajovou v M-XI
Týždeň č. 13 (11. 5. – 17. 5. 2026)
- Precvičená látka: Grafy: bipartitné a eulerovské grafy
- Prednáška: planárne grafy, úvod do farbení
Týždeň č. 14 (18. 5. – 22. 5. 2026)
- Precvičená látka: Pravdepodobnosť
- Prednáška: farbenia grafov, generujúce funkcie (rozširujúce učivo)