podzim 2012
MB103    Matematika III
Čas: 100 minut
Jméno: Místnost: 3. vnitrosemestrální písemka
list   c  _i i_l I uco   c  _i i_l  _i ll  j ľ  _i c  _i ll  j c  _i    body   c  _i i_l  _j ll j
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Příklad 1
1. Nakreslete pěstěný strom s kódem 0001001011100101001111 15 bodů
2. Určete, kolik nejvýše hran můžeme přidat do následujícího grafu tak, aby neobsahoval trojúhelník (podgraf izomorfní C3) a byl rovinný. Své tvrzení dokažte a uveďte příklad takového maximálního grafu.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
podzim 2012
MB103    Matematika III
Čas: 100 minut
Jméno: Místnost: 3. vnitrosemestrální písemka
E
list   c  _i ^h^h uco   c  _i i_l  _i ll  j ľ  _i ľ  _i ll  j c  _i    body   c  _i i_l  _j ll j
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Nechť M = {1, 2,..., n}. Uvažujme graf G, jehož vrcholy budou všechny dvou- Přiklad 2 prvkové podmnožiny množiny M. Hranou spojíme ty vrcholy, které mají neprázdný 10 bodů
průnik. Dokažte, že pro každé přirozené číslo n > 2 je graf G souvislý.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
podzim 2012
MB103    Matematika III
Čas: 100 minut
Jméno:
Místnost:
3. vnitrosemestrální písemka
list     c -_i
3
body   c -_i l  j ĺ j
Oblast strojově snímatelných informací. Své U ČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Stručně popište Ford-Fulkersonův algoritmus na hledání maximálního toku a použijte ho k nalezení maximálního párování v následujícím bipartitním grafu. Nalezením minimálního řezu zdůvodněte, proč je vámi nalezené párování skutečně maximální.
Příklad 3
15 bodů
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.
podzim 2012
MB103    Matematika III
Čas: 100 minut
Jméno:
Místnost:
3. vnitrosemestrální písemka
list     c -_i
H
body   c -_i l  j ĺ j
Oblast strojově snímatelných informací. Své U ČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
1. Určete, kolik nejméně hran musíme přidat do grafu na obrázku, aby byl eulerovský. Své tvrzení zdůvodněte.
Příklad 4
10 bodů
2. Uveďte příklad grafu na šesti vrcholech, který bude eulerovský a zároveň bude jeho doplněk eulerovský. Své tvrzení zdůvodněte, případně dokažte, že takový graf neexistuje.
Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.