# 18.5.2018 Fiala

<{ForumPost(poster="awk", timestamp=2018-06-23 08:43:46)}>
1. Zformulujte rekurenci pro výpočet koster grafu.  
Má-li graf úplný bipartitiní graf $K_{m,n}$ celkem $m^{n-1} n^{m-1}$ koster (tento předpoklad berte jako fakt), kolik má koster graf vzniklý z $K_{m,n}$ odebráním jedné hrany?
1. Definujte pojem zlepšující cesta.  
Kolik řezů a kolik elementárních řezů má síť, která vznikne sjednocením cesty délky $5$ mezi zdrojem a stokem s podobnou cestou délky $8$ (tj. síť má celkem $13$ vrcholů i hran).
1. Definujte kombinatorickou kouli.  
Určete objem kombinatorické koule $B((1,2,3)^T,2)$, je-li abeceda sedmiprvková $\{1,2,\dots,7\}$.
1. Zformulujte a dokažte větu o duálním systému k projektivní rovině.
1. Sepište přehledově, co víte o systémech různých reprezentantů.  
(Uveďte definice pojmů, tvrzení, algoritmy, příklady a souvislosti. Důkazy tvrzení a argumenty dokazující korektnost algoritmů uvádět nemusíte.)
1. Najděte vzorec pro vytvořující funkci posloupnosti čísel $a_0,a_1,\dots$ definované pomocí následujících rekurencí:  
$$a_0 = 2$$  
$$a_n = 1 + 3 \sum _{i=0}^{n-1} a_i$$  
Najděte vzorec v uzavřeném tvaru pro $a_n$.
1. Rozhodněte, zdali může existovat dvousouvislý graf na $n$ vrcholech a s $m$ hranami, který má méně než $2(m - n)$ kružnic (jako ne nutně indukované podgrafy).

<{/ForumPost}>