Zkouška 11.6.2013

Na 4 příklady jsme měli hodinu - docela málo, podle mě

• 10b Počet hran v grafu bez $C_4$, důkaz

• 10b $\delta (G)$ budiž nejmenší stupneń vrcholu v $G$. Dokažte, že pokud $\delta (G) \geq \frac{|V|}{2}$, pak je graf hranově $\delta (G)$ souvislý

• 5b Vytvořující funkce pro $-1, 3, -5, .... (-1)^n(2n-1)$, nebo možná $1, -3, 5, ...$

• 5b Porovnat růst nějakých funkcí, myslím $\binom{4n}{2n}, n^{n/2}, 3^{3n}$

Protože to dopadlo mizerně, byla trojka za 10, jinak je polovinu. Většina lidí šla na ústní, dosažené maximum bylo 20b

Řešení úloh:

• standard podle Kapitol, za formulaci a hrubou myšlenku jsem dostal asi polovinu

• dá se dělat třeba tak, že si vezmete řez veliký $\delta (G) - 1$ a koukáte se, kolik hran vlastně vychází z komponenty menší než $\frac{|V|}{2}$

• jednoduché řešení je vzít si $\frac{1}{1-x}$, zderivovat, posunout a sečíst se sebou sama, tím máte lichá čísla. Pak dosadit $-x$ za $x$ a doladit

• nejsem si jistý zadáním, nebudu se v tom šťourat, ale stačilo převést binomiál na exponenciální odhad