Basic course for program of study on mathematics. Elements of
set theory (sets, relations), introduction to combinatorics and graph
theory.
Poslední úprava: T_KTI (03.04.2001)
Literatura
P.Štěpánek, B.Balcar: Teorie množin, Academia Praha 1986
J.Matoušek, J.Nešetřil: Kapitoly z diskrétní matematiky, MATFYZPRESS 1996
J.Nešetřil: Kombinatorika I, grafy, SPN Praha 1983
Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (16.05.2012)
Sylabus -
Pojem množiny (Cantor), jazyk teorie množin, formule. Popis množiny výčtem nebo jako množiny prvků \"dané vlastnosti\". Základní operace s množinami (vč. potence a sumy) a jejich vlastnosti. Kartézský součin, (binární) relace, skládání relací. Funkce, funkce prostá a na. Vlastnosti relací (reflexivita, symetrie,...). Relace ekvivalence na množině, rozklad množiny, vzájemný vztah, příklady. Uspořádání, lineární uspořádání, největší/nejmenší, maximální/minimální,... prvek, příklady. Izomorfizmus množin vzhledem k relacím. Dobré uspořádání. Dobré uspořádání přirozených čísel podle velikosti, princip indukce pro přirozená čísla. Kombinatorické počítání. Počet zobrazení (prostých zobrazení) n-prvkové do m-prvkové množiny, počet podmnožin n-prvkové množiny. Variace, permutace, kombinace. Kombinační čísla, binomická věta. Princip inkluze a exkluze. Definice grafu, základní terminologie, izomorfizmus grafů. Stupeň uzlu, skóre grafu. Cesty v grafu, souvislost, komponenty, hledání nejkratší cesty. Metrika v grafu a pojmy z ní odvozené. Stromy, jejich charakterizace a vlastnosti, počet stromů na dané množině, kostra grafu, hledání minimální kostry. Izomorfizmus stromů, kódování stromů. Rovinné grafy, Eulerova formule a její důsledky. Obarvení rovinného grafu pěti barvami.
Poslední úprava: T_KTI (10.04.2001)
Basic course for program of study on mathematics. Elements of
set theory (sets, relations), introduction to combinatorics and graph
