1
Písemná zkouška MA010 Grafy: 19.12. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1). Dány jsou následující čtyři jednoduché grafy na 10 vrcholech každý.
A : s s
s
s
ss
s
s
s s
B : s s
s
s
ss
s
s
s s
C : s s
s
s
ss
s
s
s s
D : s s
s
s
ss
s
s
s s
Vašim úkolem je mezi nimi najít všechny isomorfní dvojice. Pro každou isomorfní dvojici vyznačte
bijekci mezi vrcholy číslováním, pro každou neisomorfní dvojici zdůvodněte rozdíl mezi grafy.
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
2
Písemná zkouška MA010 Grafy: 19.12. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2). Je dán jednoduchý graf na 10 vrcholech:
s s
s
s
s
s s
s
s
s
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) Jak velká je jeho největší nezávislá množina?
s s
s
s
s
s s
s
s
s
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
s s
s
s
s
s s
s
s
s
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
s s
s
s
s
s s
s
s
s
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
s s
s
s
s
s s
s
s
s
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
3
Písemná zkouška MA010 Grafy: 19.12. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3). Popište (jakýkoliv) souvislý jednoduchý graf, který má přesně 2017 koster a přitom neobsahuje jako
podgraf kružnici délky 2017. Nezbytnou součástí řešení je i důkaz, proč váš graf má přesně 2017
koster.
(Asi budete zklamáni, ale 2017 i 1009 jsou prvočísla.)
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
4
Písemná zkouška MA010 Grafy: 19.12. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4). Dokažte platnost následujícího tvrzení:
Každý souvislý 8-regulární graf (tj. každý vrchol stupně 8) obsahuje souvislý 6-regulární podgraf.
(Nápad: Všimněte si, že náš graf je nakreslitelný jedním tahem. . . )
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
5
Písemná zkouška MA010 Grafy: 19.12. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1). Dány jsou následující čtyři jednoduché grafy na 10 vrcholech každý.
A : s s
s
s
ss
s
s
s s
B : s s
s
s
ss
s
s
s s
C : s s
s
s
ss
s
s
s s
D : s s
s
s
ss
s
s
s s
Vašim úkolem je mezi nimi najít všechny isomorfní dvojice. Pro každou isomorfní dvojici vyznačte
bijekci mezi vrcholy číslováním, pro každou neisomorfní dvojici zdůvodněte rozdíl mezi grafy.
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
6
Písemná zkouška MA010 Grafy: 19.12. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2). Je dán jednoduchý graf na 10 vrcholech:
s
s
s
s
s
s
s
s
s
s
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) Jak velká je jeho největší nezávislá množina?
s
s
s
s
s
s
s
s
s
s
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
s
s
s
s
s
s
s
s
s
s
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
s
s
s
s
s
s
s
s
s
s
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
s
s
s
s
s
s
s
s
s
s
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
7
Písemná zkouška MA010 Grafy: 19.12. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3). Popište (jakýkoliv) souvislý jednoduchý graf, který má přesně 2017 koster a přitom neobsahuje jako
podgraf kružnici délky 2017. Nezbytnou součástí řešení je i důkaz, proč váš graf má přesně 2017
koster.
(Asi budete zklamáni, ale 2017 i 1009 jsou prvočísla.)
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
8
Písemná zkouška MA010 Grafy: 19.12. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4). Dokažte platnost následujícího tvrzení:
Každý souvislý 8-regulární graf (tj. každý vrchol stupně 8) obsahuje souvislý 6-regulární podgraf.
(Nápad: Všimněte si, že náš graf je nakreslitelný jedním tahem. . . )
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
9
Písemná zkouška MA010 Grafy: 19.12. 2007, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1). Dány jsou následující čtyři jednoduché grafy na 10 vrcholech každý.
A : s s
s
s
ss
s
s
s s
B : s s
s
s
ss
s
s
s s
C : s s
s
s
ss
s
s
s s
D : s s
s
s
ss
s
s
s s
Vašim úkolem je mezi nimi najít všechny isomorfní dvojice. Pro každou isomorfní dvojici vyznačte
bijekci mezi vrcholy číslováním, pro každou neisomorfní dvojici zdůvodněte rozdíl mezi grafy.
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
10
Písemná zkouška MA010 Grafy: 19.12. 2007, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2). Je dán jednoduchý graf na 10 vrcholech:
s
s
s
s
s
s
s
s
s
s
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) Jak velká je jeho největší nezávislá množina?
s
s
s
s
s
s
s
s
s
s
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
s
s
s
s
s
s
s
s
s
s
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
s
s
s
s
s
s
s
s
s
s
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
s
s
s
s
s
s
s
s
s
s
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
11
Písemná zkouška MA010 Grafy: 19.12. 2007, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3). Popište (jakýkoliv) souvislý jednoduchý graf, který má přesně 2017 koster a přitom neobsahuje jako
podgraf kružnici délky 2017. Nezbytnou součástí řešení je i důkaz, proč váš graf má přesně 2017
koster.
(Asi budete zklamáni, ale 2017 i 1009 jsou prvočísla.)
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
12
Písemná zkouška MA010 Grafy: 19.12. 2007, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4). Dokažte platnost následujícího tvrzení:
Každý souvislý 8-regulární graf (tj. každý vrchol stupně 8) obsahuje souvislý 6-regulární podgraf.
(Nápad: Všimněte si, že náš graf je nakreslitelný jedním tahem. . . )
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
13
Písemná zkouška MA010 Grafy: 19.12. 2007, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1). Dány jsou následující čtyři jednoduché grafy na 10 vrcholech každý.
A : s s
s
s
ss
s
s
s s
B : s s
s
s
ss
s
s
s s
C : s s
s
s
ss
s
s
s s
D : s s
s
s
ss
s
s
s s
Vašim úkolem je mezi nimi najít všechny isomorfní dvojice. Pro každou isomorfní dvojici vyznačte
bijekci mezi vrcholy číslováním, pro každou neisomorfní dvojici zdůvodněte rozdíl mezi grafy.
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
14
Písemná zkouška MA010 Grafy: 19.12. 2007, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2). Je dán jednoduchý graf na 10 vrcholech:
s
s
s
s
s
s
s
s
s
s
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) Jak velká je jeho největší nezávislá množina?
s
s
s
s
s
s
s
s
s
s
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
s
s
s
s
s
s
s
s
s
s
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
s
s
s
s
s
s
s
s
s
s
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
s
s
s
s
s
s
s
s
s
s
(Hodnocení 16 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
15
Písemná zkouška MA010 Grafy: 19.12. 2007, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3). Popište (jakýkoliv) souvislý jednoduchý graf, který má přesně 2017 koster a přitom neobsahuje jako
podgraf kružnici délky 2017. Nezbytnou součástí řešení je i důkaz, proč váš graf má přesně 2017
koster.
(Asi budete zklamáni, ale 2017 i 1009 jsou prvočísla.)
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
16
Písemná zkouška MA010 Grafy: 19.12. 2007, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
16+16+20+20 bodů. Řešení musí být na tomtéž listu
papíru jako je zadání, při nedostatku místa použijte
druhou stranu papíru. Každý list papíru musíte podepsat!
Je zakázáno použít kalkulačky a jiné el. přístroje
včetně mobilů. Pracujte samostatně. Povolen je 1 list
A4 vlastnoručně psaných poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4). Dokažte platnost následujícího tvrzení:
Každý souvislý 8-regulární graf (tj. každý vrchol stupně 8) obsahuje souvislý 6-regulární podgraf.
(Nápad: Všimněte si, že náš graf je nakreslitelný jedním tahem. . . )
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)