Balko 10.1.2023

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.
ondrasek1010
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 25. 5. 2022 14:37
Typ studia: Informatika Bc.

Balko 10.1.2023

Příspěvek od ondrasek1010 »

1) Definujte vytvořující funkci posloupnosti. Jaká posloupnost je určena funkcí \frac{1}{(1-2x^3)}?
2) Definujte most a artikulaci v grafu. Kolik mostů má graf s n vrcholy a n+1 hranami, ve kterém se vyskytuje kružnice nejvýše délky 3
3) Definujte blokový kód a jeho parametry. Existuje kód s parametry (6, 2, 2)3?
4) Definujte a dokažte ramseyovu větu pro p-tice
5) Napište vše co víte o latinských čtvercích (bez důkazů, jen se na ně rámcově zeptal ústně)

Řešení:
1) (1, 0, 0, 2, 0, 0, 4, 0, 0, 8, 0, 0,...) - dosazení 2x za x, dosazení x^3 za x
2) n - 5, důkaz přes eulerovu formuli pro stromy, každý strom na n vrcholech má n-1 hran, do stromu tedy doplníme 2 hrany, čímž vytvoříme 2 trojúhelníky (nesmí vzniknout čtyřcyklus). Tím vznikne 6 hran, které nejsou mosty, zbytek hran mosty jsou.
3) existuje, stačí libovolný vymyslet

-------------------------------------------

1) obecna binomicka veta a koeficient u x^30 v (1-6x)^(-5)
2) definice hranove a vrcholove 2-souvislosti + urcit hranovou a vrcholovou souvislost konkretniho grafu na obrazku
3) 3. priklad vzoroveho zadani...hammingova vzdalenost
4) Ramsey pro grafy (=barveni dvojic) a k barev (vcetne k=2)
5) vse o KPR

-------------------------------------------

- Definujte sit, tok, velikost toku. Urcete max. tok v konkretni siti (nejaka krychle).
- Definujte system ruznych reprezentantu. Mame kvadry v prostoru, vime ze kazdy vrchol je sdileny s max. 6 dalsimi kvadry. Existuje SRR? (kazdemu kvadru priradit vrchol)
- Dokazte vetu o dualnim systemu KPR
- Vse o samoopravnych kodech

-------------------------------------------

1) Definujte vytvořující funkci posloupnosti. Jaká posloupnost je určena funkcí 1/(1-2x^3)?
2) def. vrcholové k-souvislosti, je úplný bipartitní Kn,m vrcholově k-souvislý?
3) def. R(k,l), horní dolní odhad R(k,k) pomocí R(k-1,k-1) a R(k,k-2)
4) rozšíření lat. obdélníku na lat. čtverec
5) vše o samoopravných kódech
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“