Definujte pojmy "generující matice" a "kontrolní matice" lineárního kódu.
Následující matice je generující maticí lineárního kódu C.
1 0 1 0 1
0 1 0 1 0
Jaké rozměry bude mít kontrolní matice kódu C? Jak bude vypadat? [5]Formulujte a dokažte Spernerovu větu o nezávislém množinovém systému. [10]
Definujte pojmy "vrcholová souvislost" a "hranová souvislost". Co znamená, když se řekne, že graf G je vrcholově (resp. hranově) k-souvislý. Může existovat graf, který je hranově 5-souvislý, ale není vrcholově 5-souvislý (a zdůvodněte proč)? [5]
Definujte "párování" a "vrcholové pokrytí". Formulujte a dokažte Königovu-Egervaryho větu týkající se těchto pojmů. [10]
Bodování klasicky odstupňované po pěti bodech, ústní dobrovolná. Kdo nedosáhne na trojku, ale má alespoň 10 bodů, může ještě na ústní (resp. musí :D ).
Matice má rozměr 3×5. Může vypadat takto:
1 1 1 1 0
0 1 1 1 1
0 1 0 1 0Takový graf existuje - například dva grafy K<sub>6</sub>, které mají společný jeden vrchol. Vrcholová souvislost je 1, hranová souvislost je 5.