1. 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]
2. Formulujte a dokažte Spernerovu větu o nezávislém množinovém systému. [10]
3. 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]
4. 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í
).
1. Matice má rozměr 3×5. Může vypadat takto:
1 1 1 1 0
0 1 1 1 1
0 1 0 1 0
3. Takový graf existuje - například dva grafy K
6, které mají společný jeden vrchol. Vrcholová souvislost je 1, hranová souvislost je 5.
1. 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]
2. Formulujte a dokažte Spernerovu větu o nezávislém množinovém systému. [10]
3. 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]
4. 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 ).
1. Matice má rozměr 3×5. Může vypadat takto:
1 1 1 1 0
0 1 1 1 1
0 1 0 1 0
3. Takový graf existuje - například dva grafy K[sub]6[/sub], které mají společný jeden vrchol. Vrcholová souvislost je 1, hranová souvislost je 5.