18.5.2018 Fiala

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?

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).

Definujte kombinatorickou kouli.
Určete objem kombinatorické koule $B((1,2,3)^T,2)$, je-li abeceda sedmiprvková $\{1,2,\dots,7\}$.

Zformulujte a dokažte větu o duálním systému k projektivní rovině.

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.)

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$.

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).