od awk » 23. 6. 2018 08:43
- Zformulujte rekurenci pro výpočet koster grafu.
Má-li graf úplný bipartitiní graf 
celkem 
koster (tento předpoklad berte jako fakt), kolik má koster graf vzniklý z 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 
mezi zdrojem a stokem s podobnou cestou délky 
(tj. síť má celkem 
vrcholů i hran).
- Definujte kombinatorickou kouli.
Určete objem kombinatorické koule ^T,2))
, je-li abeceda sedmiprvková 
.
- 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
definované pomocí následujících rekurencí:
Najděte vzorec v uzavřeném tvaru pro 
.
- Rozhodněte, zdali může existovat dvousouvislý graf na
vrcholech a s 
hranami, který má méně než )
kružnic (jako ne nutně indukované podgrafy).
[list=1]
[*]Zformulujte rekurenci pro výpočet koster grafu.
Má-li graf úplný bipartitiní graf [latex]K_{m,n}[/latex] celkem [latex]m^{n-1} n^{m-1}[/latex] koster (tento předpoklad berte jako fakt), kolik má koster graf vzniklý z [latex]K_{m,n}[/latex] 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 [latex]5[/latex] mezi zdrojem a stokem s podobnou cestou délky [latex]8[/latex] (tj. síť má celkem [latex]13[/latex] vrcholů i hran).
[*]Definujte kombinatorickou kouli.
Určete objem kombinatorické koule [latex]B((1,2,3)^T,2)[/latex], je-li abeceda sedmiprvková [latex]\{1,2,\dots,7\}[/latex].
[*]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 [latex]a_0,a_1,\dots[/latex] definované pomocí následujících rekurencí:
[latex]a_0 = 2[/latex]
[latex]a_n = 1 + 3 \sum _{i=0}^{n-1} a_i[/latex]
Najděte vzorec v uzavřeném tvaru pro [latex]a_n[/latex].
[*]Rozhodněte, zdali může existovat dvousouvislý graf na [latex]n[/latex] vrcholech a s [latex]m[/latex] hranami, který má méně než [latex]2(m - n)[/latex] kružnic (jako ne nutně indukované podgrafy).[/list]