Úvod do kombinatoriky a teórie grafov
2020/2021

Domov Kontakt Pravidlá Študijné materiály Cvičenia Domáce úlohy

Cvičenia

Cvičenie č. 1 (17. februára 2021)

• Precvičená látka: matematická indukcia, úplná matematická indukcia.
• Úlohy na precvičenie (matematická indukcia).
• Prednáška: Dirichletov princíp (základná a frekvenčná forma)
• 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).

Cvičenie č. 2 (24. februára 2020)

• Precvičená látka: Dirichletov princíp (základná a frekvenčná forma), optimalizačné kombinatorikcé úlohy.
• Úlohy na precvičenie (dirichletov princíp).
• 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.
• Prednáška: pravidlo súčtu a súčinu, variácie s opakovaním.

Cvičenie č. 3 (3. marca 2021)

• Precvičená látka: základné enumeračné pravidlá: pravidlo súčtu, súčinu, mocnenia, rozdielu.
• Úlohy na precvičenie (základné 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 a zopár vlastností).

Cvičenie č. 4 (10. marca 2021)

• Precvičená látka: štandardné kombinatorické konfigurácie: variácie s opakovaním aj bez, kombinácie bez opakovania.
• Úlohy na precvičenie.
• Video s niekoľkými vyriešenými úlohami k cvikám.

Cvičenie č. 5 (17. marca 2021)

• Precvičená látka: kombinatorické dôkazy binomických identít.
• Úlohy na precvičenie.
• Prednáška: identity a nerovnosti s kombinačnými číslami, úvdo do kombinácií bez opakovania

Cvičenie č. 6 (24. marec 2021)

• Precvičená látka: počítanie súm
• Úlohy na precvičenie.
• Prednáška nebola.

Cvičenie č. 7 (31. marec 2021)

• Precvičená látka: štandardné kombinatorické konfigurácie 2: kombinácie s opakovaním, permutácie s opakovaním, rôzne úlohy
• Úlohy na precvičenie.
• 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).
• V skriptách sekcia 3. 6 Kombinácie s opakovaním, permutácia s opakovaním (str. 45 – 47).

Cvičenie č. 8 (7. apríl 2021)

• Precvičená látka: opakovanie kombinatorických konfigurácií, úvod do princípu inklúzie a exklúzie.
• Úlohy na precvičenie (princíp inklúzie a exklúzie).
• Prednáška nebola

Cvičenie č. 9 (14. apríl 2021)

• Precvičená látka: princíp zapojenia a vypojenia.
• Úlohy na precvičenie (princíp inklúzie a exklúzie).
• Odporúčané čítanie: oddiel o princípe zapojenia a vypojenia z knihy Matouška a Nešetřila (v treťom vydaní má číslo 3.6).
• Ďalšie odporúčané čítanie: relevantné oddiely kapitoly o princípe zapojenia a vypojenia z Brualdiho knihy (táto kapitola má v štvrtom vydaní číslo 6).
• Prednáška: polynomická veta, princíp zapojenia a vypojenia

Cvičenie č. 10 (21. apríl 2021)

• Cvičenie nebude – dekanské voľno (ŠVK)
• Prednáška: Príklad o klobúkoch na PIE, asymptotické odhady
• 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).

Cvičenie č. 11 (28. apríl 2021)

• Precvičená látka: asymptotické odhady.
• Úlohy na precvičenie.

Cvičenie č. 12 (5. máj 2021)

• Precvičená látka: teória grafov: úvod, základné pojmy, sledy, súvislosť, stromy, bipartitné grafy
• Úlohy na precvičenie.
• Ď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.

Cvičenie č. 13 (6. máj 2020)

• Úlohy na precvičenie.
• Precvičená látka: eulerovské grafy, opakovanie grafov
• Prednáška: eulerovské grafy, ich ekvivalentné charakterizácie