# 12.6.2015 Jelínek

<{ForumPost(poster="nikdo", timestamp=2015-06-13 12:41:36)}>
Termín 12.6.2015 (Jelínek):  
  
**1) Porovnejte následující funkce podle rychlosti jejich růstu:** *\[5 bodů]*  
a) $n^{\sqrt{n}}$, b) $\binom{2^n}{n}$, c) $(3n)!$  
** ta první funkce byla trošku jinak, ale víceméně takhle*  
  
**2) Zformulujte a dokažte König-Egerváryho větu o velikosti párování a vrcholového pokrytí.** *\[10 bodů]*  
  
**3) Definujte (n,k,d)-kód. Napište příklad (5,2,3)-kódu.** *\[5 bodů]*  
  
**4) Počet koster úplného bipartitního grafu $K_{m,n}$ (partity velikosti $m$ a $n$ vrcholů) je ... (nemusíte dokazovat). Kolik koster má graf $K_{m,n}^{-}$ vzniklý z grafu $K_{m,n}$ odebráním jedné hrany?** *\[10 bodů]*  

----

Náznak řešení:  
  
1) Buď pomocí horních a dolních odhadů funkcí (viz první cvikopřednáška), nebo analyticky přes limity (nevím, jestli uznával, ale asi jo).  
  
2) Věta a důkaz z přednášky *(20. března)*.  
  
3) Definice z přednášky *(15. května)*. Jako příklad (5,2,3)-kódu jsem si nějaký vymyslel (chce to trochu kreativity). Z definice je zřejmé, že takový kód C bude mít 2<sup>2</sup> = 4 kódových slov (vektorů) o délce 5. A každé dva se musí lišit v alespoň 3 bitech. Splňuje to například:  
  
*C={(1,1,1,1,1),(1,1,0,0,0),(0,0,1,1,0),(0,0,0,0,1)}*  
  
4) Viz přednáška *(3. dubna)*: věta o tom, kolik koster obsahujících jednu konkrétní hranu má úplný graf. Tedy výsledek je (počet koster celkem - počet koster s konkrétní hranou). Akorát pozor, protože na přednášce jsme to dělali pro úplný graf, tentokrát je to úplný bipartitní graf!
<{/ForumPost}>