Úvod do kombinatoriky a teórie grafov
2018/2019

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

Cvičenia

• Precvičená látka: matematická indukcia, úplná matematická indukcia a vlastnosť dobrého usporiadania prirodzených čísel, Dirichletov princíp (základná a frekvenčná forma).
• Úlohy na precvičenie (matematická indukcia).
• Úlohy na precvičenie (dirichletov princíp).
• 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: pravidlá súčtu, súčinu a mocnenia.
• Úlohy na precvičenie.
• Odporúčané čítanie: oddiel „Four basic counting principles” z Brualdiho knihy (v štvrtom vydaní má číslo 3.1).

• Precvičená látka: štandardné kombinatorické konfigurácie I (variácie s opakovaním a bez opakovania, permutácie bez opakovania, kombinácie bez opakovania).
• Úlohy na precvičenie.
• 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).

• Precvičená látka: kombinatorické dôkazy binomických identít.
• Úlohy na precvičenie.

• Precvičená látka: binomická veta, jednoduché sumy s kombinačnými číslami, použitie binomickej vety na dokazovanie identít.
• Ú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).

• Precvičená látka: štandardné kombinatorické konfigurácie II (kombinácie s opakovaním, permutácie s opakovaním, rôzne úlohy).
• Úlohy na precvičenie.

• Precvičená látka: princíp zapojenia a vypojenia.
• Úlohy na precvičenie.
• 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).

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

• Precvičená látka: opakovanie

• Precvičená látka: základné pojmy z teórie grafov, súvislosť, izomorfizmus grafov
• Úlohy na precvičenie.

• Precvičená látka: vrcholová a hranová súvislosť
• Úlohy na precvičenie. Pre tento kurz sú relevantné len príklady po príklad s číslom 33.

• Precvičená látka: stromy, eulerovské grafy, hamiltonovské grafy, planárne graf
• Úlohy na precvičenie.