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ů ]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ů ]
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ů ]
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ů ]