Ú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í).
Poslední úprava: T_KAM (06.05.2001)
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).
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)
Zápočet bude udělen za zisk dostatečného počtu bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, popř. docházku. Přesné podmínky se však individuálně liší u jednotlivých vyučujících a budou popsány níže. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů. Získání zápočtu je nutnou podmínkou pro skládání zkoušky.
J. Amemori: Je potřeba získat 2/3 bodů za domácí úkoly.
M. Balko: Na zápočet je třeba získat alespoň 90 bodů, přičemž celkem 80 lze získat za dvě písemky a zhruba 80 za průběžně zadávané domácí úkoly.
M. Berg: K udělení zápočtu je potřeba získat alespoň 60 bodů. Celkem 50 bodů půjde získat z domácích úkolů a 25 bodů za každou ze dvou písemek. Další bonusové body je možné získat za aktivitu na cvičení.
J. Pekárek: Je potřeba získat dostatečný počet bodů za domácí úkoly.
J. Syrovátková: Na zápočet je potřeba celkem 280 bodů. Budou se psát 3 písemky, každá za 100 bodů, dále domácí úkoly celkem za 100 bodů. Další body je možné získat za aktivitu na cvičení (dobrovolné domácí úkoly u tabule a podobně).
P. Zeman: Je potřeba získat aspoň 100 bodů za domácí úkoly.
Poslední úprava: doc. Hans Raj Tiwary, M.Sc., Ph.D. (15.10.2018)
Hans Raj Tiwary:
There will be homeworks and one small test for the credit for the tutorial.
It is required to obtain a pass in half of the homeworks and obtain 50% of
the points in the test to pass the tutorial.
The material for the tests will be the one covered during the lectures.
Obtaining the credit is necessary before the final exam.
There is provision for repeated attempts for the credit.
Literatura -
Poslední úprava: G_I (25.01.2007)
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, nakladatelstvi Carolinum, Praha, 2000
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (22.11.2012)
J. Matousek, J. Nesetril: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.
Požadavky ke zkoušce -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)
Zkouška se skládá z písemné a ústní části. Ústní část proběhne formou diskuse řešení písemné části a případných doplňujících otázek.
Poslední úprava: doc. Hans Raj Tiwary, M.Sc., Ph.D. (12.10.2017)
Hans Raj Tiwary:
There will be one written exam for the main course, with oral part where the students explain
their solutions at the end of the exam. The material for the exam will be the same as taught in the lecture.
Sylabus -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
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.
Částečné uspořádání, řetězce a antiřetězce, věta o dlouhém a širokém, Erdösovo-Szekeresovo lemma o monotónní podposloupnosti.
Rozšiřující témata: hra HEX; věta o skóre.
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
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.
