7. 6. 2019 - Jelínek

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.
petros
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 7. 6. 2019 12:11
Typ studia: Informatika Bc.

7. 6. 2019 - Jelínek

Příspěvek od petros »

1. Napište definici pojmů "generující matice" a "kontrolní matice" lineárního kódu. Nechť C je lineární kód, jehož generující matice vypadá následovně:
1 1 1 0 0 0
0 0 0 1 1 1
Jaké rozměry bude mít kontrolní matice kódu C? Jak bude ta kontrolní matice vypadat? [ 5 bodů ]

2. Zformulujte a dokažte Ramseyovu větu ve verzi, která mluví o existenci kliky a nezávislých množin v (kořenových) grafech. [ 10 bodů ]

3. Napište definici pojmu "latinský čtverec" a napište, co to znamená, že dva latinské čtverce jsou ortogonální. Zformulujte větu, která popisuje souvislost mezi ortogonalitou latinských čtverců a existenci konečné projektivní roviny řádu n. [ 5 bodů ]

4. Pro m >= 1 a n >= 1 označme Kn,m úplný bipartitní graf s partitami velikosti m a n. Platí, že graf Km,n má přesně m^(n-1)*n^(m-1) koster (to však nemusíte dokazovat, berte to jako fakt). S využitím tohoto vzorečku odvoďte, kolik koster má graf Kn,m- vzniklý z grafu Kn,m odstraněním jedné hrany. [ 10 bodů ]
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“