Diskrétní matematika

Přednáška ve středu 14:00, S5

Co se dosud probralo:

• 2. 10. Několik motivačních příkladů, základní značení, sumy, součiny, množinové operace. Jednoduchý příklad důkazu indukcí.
• 9. 10. Relace, jejich skládání, inverzní relace. Funkce a jejich speciální případy (prosté, na, bijektivní). Složením prostých funkcí vznikne prostá funkce, podobně pro funkce na a pro bijekce. Každá funkce může vzniknout složením funkce na s prostou funkcí. Reflexivita, tranzitivita, symetrie a antisymetrie relací. Ekvivalence, jejich třídy a základní vlastnosti.
• 16. 10. Částečná uspořádání, částečně uspořádané množiny, lineární uspořádání, Hasseho diagramy. Pojem minimálního, maximálního, nejmenšího a největšího prvku. Antiřetězce a řetězce, věta o dlouhém a širokém, Erdos-Szekeresova věta o monotónní podposloupnosti. Jednoduché kombinatorické počítání.
• 23. 10. Děkanský den: přednáška odpadla.
• 30. 10. Princip inkluze a exkluze, jeho aplikace na počítání permutací bez pevného bodu ("problém šatnářky"). Úvod do diskrétní pravděpodobnosti: diskrétní pravděpodobnostní prostor, jevy, nezávislé jevy, podmíněná pravděpodobnost, náhodná veličina, střední hodnota.
  
• 6. 11. Věta o úplné pravděpodobnosti, Bayesova věta, pravděpodobnostní rozdělení náhodné veličiny, linearita střední hodnoty, distribuční funkce. Grafy: matice incidence, matice sousednosti, izomorfismus grafů, úplný graf, kružnice, cesta, bipartitní graf, úplný bipartitní graf.
• 13. 11. Základní grafové pojmy: podgraf, indukovaný podgraf, komponenta souvislosti, souvislý graf, vzdálenost v grafu, stupeň, skóre. Princip sudosti. Eulerovské grafy.
• 20. 11. Jednoduché grafové operace: mazání hrany či vrcholu, přidání hrany, dělení hrany, kontrakce hrany. Stromy: existence listu, ekvivalentní charakterizace. Kostry grafů. Barvení grafů.
• 27. 11. Souvislost mezi barevností a největším stupněm, a mezi barevností a největším úplným podgrafem. Degenerovanost grafu, její ekvivalentní definice a její souvislost s barevností. Rovinné grafy. Základní pojmy z topologie roviny: oblouk, topologická kružnice, oblouková souvislost, Jordanova věta.
• 4. 12. Vlastnosti rovinných grafů: Eulerův vzorec, odhad na počet hran, nerovinnost K₅ a K_3,3. Kuratowského věta (bez důkazu těžké implikace).
• 11. 12. Barvení map a jeho souvislost s vrcholovou barevností rovinných grafů. Pětidegenerovanost rovinných grafů. Věta o pěti barvách. Mnohostěny a jejich souvislost s rovinnými grafy. Důkaz, že neexistuje víc než pět pravidelných mnohostěnů.
• 18. 12. Návrat k pravděpodobnosti: nezávislost více než dvou jevů, nezávislost náhodných veličin, Markovova nerovnost, rozptyl a směrodatná odchylka, Čebyševova nerovnost. Příklady důležitých pravděpodobnostních rozdělení: Bernoulliovo, rovnoměrné, binomické, Poissonovo.
• 8. 1. Věta o skóre. Pravděpodobností důkaz, že každý graf G=(V,E) má bipartitní podgraf s alespoň |E|/2 hranami. Konstrukce grafů bez trojúhelníku s velkou barevností.