Základní techniky:
Kombinatorické počitání:
- počítání řetězců s různými vlastnostmi
- permutace a dva pohledy na ně (pořadí vs. bijekce)
- charakteristické funkce podmnožin
- k-prvkové podmnožiny a kombinační čísla
- Binomická věta a její důsledky
Diskrétní pravděpodobnost:
- příklady úloh na pravděpodobnost
- zobecnění: diskrétní pravděpodobnostní prostor, elementární a složené jevy
- podmíněná pravděpodobnost
- věta o úplné pravděpodobnosti (rozbor případů)
- součin pravděpodobnostních prostorů
- náhodna veličina a střední hodnota
Princip inkluze a exkluze:
- problém šatnářky (permutace bez pevného bodu)
- princip inkluze a exkluze
- asymptotické odhady (faktoriál, kombinační čísla)
Grafy:
- stupeň vrcholu, regulární grafy, princip sudosti
- operace s grafy: přidání vrcholu/hrany, dělení hrany, kontrakce hrany
- odhad počtu neisomorfních grafů na N vrcholech
- podgrafy a indukované podgrafy
- cesta v grafu, souvislost, komponenty
- vzdálenost v grafu, metrika
- matice sousednosti a incidence grafu
- mocniny matice sousednosti počítají sledy
Stromy:
- definice: strom je minimální souvislý graf
- strom je souvislý graf bez kružnic
- strom na N vrcholech má N-1 hran
- existence listu (průměrný stupeň je menší než 2)
- přidání/odebrání listu nezmění, zda je graf stromem, a indukce přes listy
- věta o ekvivalentních charakterizacích stromu
Relace a funkce:
- uspořádané dvojice a k-tice
- operace s relacemi (skládání)
Ekvivalence:
- vlastnosti relací (reflexivita, symetrie, transitivita)
- popis pomocí ekvivalenčních tříd
Uspořádání:
- částečné a lineární uspořádání
- největší/nejmenší, maximální/minimální prvek, řetězec/antiřetězec, supremum/infimum
- na konečných množinách: existence minimálního prvku, lineární rozšíření
- isomorfismus vzhledem k relacím
- součin uspořádání, inkluze je mocnina dvojprvkového uspořádání
- věta o dlouhém a širokém (existence velkého řetězce nebo antiřetězce)
- aplikace: Erdősova-Szekeresova věta o monotónní podposloupnosti
Kreslení grafů do roviny:
- neformální definice nakreslení a jeho stěn
- cesty a kružnice jsou rovinné, stromy taktéž
- graf K_5 není rovinný (rozbor případů)
- kreslení na sféru a stereografická projekce
- horní odhad počtu hran rovinného grafu
- existence vrcholu stupně nejvýše 5
- Kuratowského věta (bez důkazu)
Barvení grafů:
- Historie: problém čtyř barev
- dualita rovinných grafů, převod barvení stěn na barvení vrcholů
- dobré obarvení grafu, barevnost
- 2-obarvitelné grafy jsou ty bipartitní
- barvení indukcí: stromy jsou 2-obarvitelné, rovinné grafy jsou 6-obarvitelné
Vlastnosti grafů:
- sledy a tahy v grafech, eulerovské tahy
- věta o existenci uzavřeného eulerovského tahu
- orientované grafy a multigrafy
- silná a slabá souvislost orientovaných grafů
- rozšíření eulerovských tahů na orientované multigrafy
- dolní odhad Ramseyových čísel (pravděpodobnostní metoda)
Poslední úprava: Mareš Martin, Mgr., Ph.D. (13.10.2024)
Basic techniques:
Combinatorial counting:
- counting strings with different properties
- permutations and two views of them (order vs. bijection)
- characteristic functions of subsets
- k-element subsets and binomial coefficients
- Binomial theorem and its consequences
Discrete probability:
- example problems on probability
- generalization: discrete probability space, elementary and compound events
- total probability theorem (case analysis)
- product of probability spaces
- random variable and its expectation
Principle of inclusion and exclusion:
- the hatcheck lady problem (permutations with no fixed point)
- principle of inclusion and exclusion
- asymptotic bounds (factorial, binomial coefficients)
Graphs:
- degree of a vertex, regular graphs, handshaking lemma
- operations on graphs: adding a vertex/edge, subdividing/contracting an edge
- a bound on the number of non-isomorphic graphs on N vertices
- subgraphs and induced subgraphs
- path in a graph, connectivity, connected components
- distance in a graph, graph metric
- matrices of adjancency and incidence
- powers of adjacency matrix count walks
Trees:
- definition: a tree is a minimal connected graph
- a tree is a connected acyclic graph
- a tree on N vertices has N-1 edges
- existence of leaves (average degree is smaller than 2)
- adding/removing a leaf doesn't change if a graph is a tree; induction using leaves
- equivalent characterizations of trees
Relations and functions:
- ordered pairs and k-tuples
- cartesian product of sets
- operations on relations (composition)
Equivalence relations:
- properties of relations (reflexivity, symmetry, transitivity)
- equivalence as a relation
- characterization using equivalence classes
Orders:
- partial and linear (total) order
- minimum/maximum, minimal/maximal element, chain/antichain, supremum/infimum
- on finite sets: existence of a minimal element, linear extension
- isomorphism with respect to relations
- product of orders, inclusion is a power of a 2-element order
- existence of large chains/antichains
- application: Erdős-Szekeres theorem on existence of monotone subsequences
Planar embedding of graphs:
- informal definition of an embedding and its faces
- paths and cycles are planar and so are trees
- embedding in a sphere and stereographic projection
- upper bound on the number of edges of a planar graph
- existence of a vertex of degree at most 5
- Kuratowski's theorem (without proof)
Graph coloring:
- history: the 4 color problem
- duality of plane graphs, reduction of coloring of faces to coloring of vertices
- proper coloring, chromatic number
- 2-colorable graphs are those bipartite
- coloring by induction: trees are 2-colorable, planar graphs are 6-colorable
Graph properties:
- walks and tours in graphs, Eulerian tours
- existence of a closed Eulerian tour
- directed graphs and multigraphs
- strong and weak connectivity
- Eulerian tours in directed multigraphs
- lower bound on Ramsey numbers (probabilistic method)
Poslední úprava: Mareš Martin, Mgr., Ph.D. (13.10.2024)
|