9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 1
20 bodů
Vašim úkolem je sestrojit a nakreslit všechny neisomorfní lesy (jednoduché acyklické
grafy) na 6 vrcholech.
Rozepište ve stručných a srozumitelných bodech, jak jste postupovali. Všechny kroky také
správně zdůvodněte. (Kromě správnosti a úplnosti odpovědí se hodnotí také systematičnost vašeho přístupu
k sestrojení požadovaných grafů, ze kterého musí vyplývat, že jste prošli všechny možnosti.)
Pište upraveně ­ řešení nejprve hledejte na vlastních papírech!
Sem přepište finální řešení vašeho příkladu, žádné čmáranice.
Lze použít i druhou stranu listu, opravující ji uvidí,
ale nebude se scanovat do IS. Také můžete
použít "pokračovací" odpovědní list.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 2
20 bodů
Je dán jednoduchý graf na 12 vrcholech:
s s
s
s
ss
s
s
s s
ss
Vašim úkolem je zodpovědět správně následující čtyři otázky o tomto grafu. V odpovědi nestačí uvést jen
správný výsledek, ale nutné je i stručné zdůvodnění jeho správnosti (na přiloženém obrázku).
a) Vyznačte v grafu některou Hamiltonovskou kružnici (procházející všemi vrcholy).
s s
s
s
ss
s
s
s s
ss
b) Jaká je barevnost tohoto grafu?
s s
s
s
ss
s
s
s s
ss
c) Jakou velikost má největší nezávislá množina v tomto grafu?
s s
s
s
ss
s
s
s s
ss
d) Jaká je nejdelší indukovaná cesta v tomto grafu?
s s
s
s
ss
s
s
s s
ss
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 3
20 bodů
Z přednášek víme, že každý jednoduchý rovinný graf musí obsahovat vrchol stupně menšího
než 6.
a) Sestrojte jednoduchý rovinný graf, který má více než 10 vrcholů, ale jen méně než 10
jeho vrcholů má stupně menší než 6.
b) Zjistěte, pro jaké nejmenší číslo b platí, že existuje jednoduchý rovinný graf s minimálním stupněm 3 a
maximálním stupněm aspoň 6, v němž nejvýše b vrcholů má stupně menší než 6.
Svou odpověď matematicky dokažte (včetně zdůvodnění, proč menší b není možné).
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 4
20 bodů
Mějme libovolný konečný graf G = (V, E). O množině hran F  E řekneme, že je
nezávislá, pokud každá souvislá komponenta podgrafu G
= (V, F) obsahuje nejvýše
jednu kružnici. (Je to tedy jiná definice nezávislosti hran v grafu, než jsme měli na
přednášce u matroidů.)
Vašim úkolem je dokázat, že množina E hran grafu G spolu s touto definicí nezávislosti tvoří matroid. (Neboli
musíte vypsat a ověřit tři axiomy nezávislých množin matroidu podle této definice.)
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška A Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 1
20 bodů
Vašim úkolem je sestrojit a nakreslit všechny neisomorfní stromy (jednoduché souvislé
acyklické grafy) na 7 vrcholech.
Rozepište ve stručných a srozumitelných bodech, jak jste postupovali. Všechny kroky také
správně zdůvodněte. (Kromě správnosti a úplnosti odpovědí se hodnotí také systematičnost vašeho přístupu
k sestrojení požadovaných grafů, ze kterého musí vyplývat, že jste prošli všechny možnosti.)
Pište upraveně ­ řešení nejprve hledejte na vlastních papírech!
Sem přepište finální řešení vašeho příkladu, žádné čmáranice.
Lze použít i druhou stranu listu, opravující ji uvidí,
ale nebude se scanovat do IS. Také můžete
použít "pokračovací" odpovědní list.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 2
20 bodů
Je dán jednoduchý graf na 12 vrcholech:
s s
s
s
ss
s
s
s s
ss
Vašim úkolem je zodpovědět správně následující čtyři otázky o tomto grafu. V odpovědi nestačí uvést jen
správný výsledek, ale nutné je i stručné zdůvodnění jeho správnosti (na přiloženém obrázku).
a) Vyznačte v grafu některou Hamiltonovskou kružnici (procházející všemi vrcholy).
s s
s
s
ss
s
s
s s
ss
b) Jaká je barevnost tohoto grafu?
s s
s
s
ss
s
s
s s
ss
c) Jakou velikost má největší nezávislá množina v tomto grafu?
s s
s
s
ss
s
s
s s
ss
d) Jaká je nejdelší indukovaná cesta v tomto grafu?
s s
s
s
ss
s
s
s s
ss
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 3
20 bodů
Z přednášek víme, že každý jednoduchý rovinný graf musí obsahovat vrchol stupně menšího
než 6.
a) Sestrojte jednoduchý rovinný graf, který má více než 10 vrcholů, ale jen méně než 10
jeho vrcholů má stupně menší než 6.
b) Zjistěte, pro jaké nejmenší číslo b platí, že existuje jednoduchý rovinný graf s minimálním stupněm 4 a
maximálním stupněm aspoň 6, v němž nejvýše b vrcholů má stupně menší než 6.
Svou odpověď matematicky dokažte (včetně zdůvodnění, proč menší b není možné).
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Příklad 4
20 bodů
Mějme libovolný konečný graf G = (V, E). O množině hran F  E řekneme, že je
nezávislá, pokud každá souvislá komponenta podgrafu G
= (V, F) obsahuje nejvýše
jednu kružnici. (Je to tedy jiná definice nezávislosti hran v grafu, než jsme měli na
přednášce u matroidů.)
Vašim úkolem je dokázat, že množina E hran grafu G spolu s touto definicí nezávislosti tvoří matroid. (Neboli
musíte vypsat a ověřit tři axiomy nezávislých množin matroidu podle této definice.)
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.
9.1. 2009 (80) MA010 písemná zkouška B Čas: 140 min
Jméno: Místnost: Souřadnice:
list učo body
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.
Pokračování řešení některého příkladu
Pokračujte zde v řešení kteréhokoliv jednoho příkladu
(samozřejmě napište, kterého, a poznačte na jeho
titulním listě), odevzdejte spolu s titulním listem.
Vyžádejte si další list pro jiný příklad.
Oblast strojově sním. informací, nezasahujte. Jen tato strana bude v IS, druhou stranu uvidí jen opravující.