Kombinatorika pro bioinformatiky

Sylabus

Základní značení, relace, ekvivalence, uspořádání.

Funkce a jejich druhy (injekce, surjekce), 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.

Základy diskrétní pravděpodobnosti.

Základní pojmy z grafů, základní typy grafů (prázdný, úplný, bipartitní atd.), izomorfismus. Cesty a kružnice v grafech, souvislost.

Stromy (různé charekterizace, existence listu), kostra grafu.

Rovinné grafy, Eulerova formule, maximální počet hran.

Barevnost grafu, d-degenerovaný graf má barevnost nejvýš d+1, 5-barevnost rovinných grafů (přes Kempeho řetězce).

Charakterizace eulerovských grafů.

Hranová a vrcholová k-souvislost, Mengerova a Ford-Fulkersonova věta.

Anotace

Základní přednáška z kombinatoriky a grafů určená pro studenty bioinformatiky.