Zadani
Definujte vrcholové pokrytí a párování v grafu G=(V,E) a formulujte Königovu-Egerváryho větu (bez důkazu) - 5 bodů
Definujte pojmy latinský čtverec a ortogonalita latinských čtverců. Napište a dokažte horní odhad na počet ortogonálních čtverců. - 10 bodů
Zformulujte ( bez důkazu ) nekonečnou Ramseyovu větu a definujte netriviální pojmy z formulace ( obarvení a homogenní množina) . - 5 bodů
Napište a dokažte nejtěsnější dolní a horní odhad na n! - 10 bodů
Reseni
vše viz Jelínkovi přednášky
Zadani
Vytvořující funkce pro posloupnost, jejíž n-tý člen je an=((-2)^n)+3
Co nejpřesnější dolní a horní odhad pro 2n nad n, který obsahuje pouze jednoduché výrazy (tzn. bez kombinačních čísel a faktorialů)
Definice systému různých reprezentantů a znění Hallovy věty (hypergrafová verze)
Znění a důkaz Cayleyho formule
Zadani
Definice Tokové sítě, toku v síti, velikosti toku a zlepšující cesty (5)
Nejtěsnější odhad na (2nCn) + důkaz. (10)
Bázi kódu tvoří vektory (10101) a (11111). Najděte jeho generující a kontrolní matici, v případě, že je neumíte najít, napište alespoň jejich rozměry. Jaká je minimální vzdálenost.(5)
Máme posloupnost zadanou rekurentně :
a_0 = 3
a_1= 1
a_n = 3a_n-1 + 2 a_n-2
Najděte její vytvořující funkci a vzorec pro a_n v uzavřeném tvaru (10)
Poznamky
Jelínek kouká na řešení velmi mírně a většinou body spíš přidává než ubírá. Důležitější než výsledek je postup. Po opravení, když něco nechápe, doptá se. Ústní zkoušky na doopravení známky bych se nebálá. V nejhorším i po zadání příkladu můžete vycouvat.