18.5.2018 Fiala

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Uživatelský avatar
awk
Matfyz(ák|ačka) level II
Příspěvky: 56
Registrován: 21. 5. 2018 18:54
Typ studia: Informatika Bc.

18.5.2018 Fiala

Příspěvek od awk »

  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?
  2. 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).
  3. Definujte kombinatorickou kouli.
    Určete objem kombinatorické koule B((1,2,3)^T,2), je-li abeceda sedmiprvková \{1,2,\dots,7\}.
  4. Zformulujte a dokažte větu o duálním systému k projektivní rovině.
  5. 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.)
  6. 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.
  7. 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).
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“