Introduction to combinatorics and graph theory. We lay stress on active knowledge of basic definitions and methods (relation, mapping, graph, exact formulation of mathematical theorems, problem solving and proofs of simple statements).
Last update: T_KAM (06.05.2001)
Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní
zvládnuti základních pojmů a metod (relace, zobrazení, graf;
přesná formulace matematických tvrzení, řešení příkladů a dokazovaní
jednoduchých tvrzení).
Literature -
Last update: doc. Mgr. Milan Hladík, Ph.D. (22.11.2012)
J. Matousek, J. Nesetril: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.
Last update: G_I (25.01.2007)
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, nakladatelstvi Carolinum, Praha, 2000
Syllabus -
Last update: doc. Mgr. Milan Hladík, Ph.D. (23.11.2012)
Basic notation, motivating examples, the concept of a proof, proof by induction.
Mappings, relations, equivalences. Permutations.
Basic combinatorial counting (the number of subsets, of subsets of size k, of all mappings, of all injective mappings, of permutations). The binomial theorem.
Probability space (at most countable, all subsets are events). Independent events, conditional probability. Random variable, distribution function. Expectation, examples of calculation.
Basic notions of graph theory, path/circuit/walk, isomorphism, etc.
Characterisation of Eulerian graphs (including directed case; strong and weak connectedness).
Trees (various characterisations, existence of a leaf).
Planar graphs, Euler's formula, maximum number of edges.
The chromatic number of a graph, characterisation of bipartite graphs, chromatic number of a d-degenerate graph is at most d+1; 5-colorability of planar graphs (using Kempe's chains).
Partial orderings, chains and antichains, large implies tall or wide, Erdös-Szekeres lemma on monotone subsequences.
Additional topics: the HEX game, score theorem.
Last update: G_I (31.05.2012)
Základní značení, motivační příklady, co je důkaz, důkaz indukcí.
Funkce, relace, ekvivalence. Permutace.
Základní kombinatorické počítání (počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých zobrazení, permutací). Binomická věta.
Princip inkluze a exkluze a jeho aplikace (šatnářka).
Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy). Nezávislé jevy, podmíněná pravděpodnost. Náhodná veličina, distribuční funkce. Střední hodnota a její výpočet. (Základní diskrétní pravděpodobnostní rozdělení).
Základní pojmy z grafù, cesta/tah/sled, izomorsmus apod.
Charakterizace eulerovských grafù (též orientovaný případ, silná a slabá souvislost).
Stromy (různé charekterizace, existence listu).
Rovinné grafy, Eulerova formule, maximální počet hran.
