28.6.2018 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.
Thrayld
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 25. 1. 2018 22:01
Typ studia: Informatika Bc.

28.6.2018 Jelínek

Příspěvek od Thrayld »

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 K6, které mají společný jeden vrchol. Vrcholová souvislost je 1, hranová souvislost je 5.
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“