Kombinatorika a grafy I - Jelinek 2019

spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

Kombinatorika a grafy I - Jelinek 2019

Příspěvek od spidoosho »

Zadani
1. 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ů
2. 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ů
3. Zformulujte ( bez důkazu ) nekonečnou Ramseyovu větu a definujte netriviální pojmy z formulace ( obarvení a homogenní množina) . - 5 bodů
4. 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
1. Vytvořující funkce pro posloupnost, jejíž n-tý člen je an=((-2)^n)+3
2. 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ů)
3. Definice systému různých reprezentantů a znění Hallovy věty (hypergrafová verze)
4. Znění a důkaz Cayleyho formule

-----------------------------------

Zadani
1. Definice Tokové sítě, toku v síti, velikosti toku a zlepšující cesty (5)
2. Nejtěsnější odhad na (2nCn) + důkaz. (10)
3. 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)
4. 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.
Odpovědět

Zpět na „Ostatní“