1
Písemná zkouška MA010 Grafy: 9.1. 2008, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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án je následující jednoduchý graf na 10 vrcholech.
s s
s
s
ss
s
s
s s
Vašim úkolem je zjistit, kolik vzájemně neisomorfních grafů může vzniknout z tohoto grafu přidáním
jednoho nového vrcholu x a (jediné) hrany z x do některého původního vrcholu. Svou odpověď aspoň
stručně zdůvodněte.
(Hodnocení 17 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
2
Písemná zkouška MA010 Grafy: 9.1. 2008, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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 11 vrcholech:
s s
s
s
s
s s
s
s
s s
Vašim úkolem je zodpovědět správně následující tř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 s
b) Nakreslete libovolný jednoduchý graf, který má stejnou posloupnost stupňů jako zadaný graf
a přitom je nesouvislý.
c) Jaká je barevnost našeho grafu? Nazapomeňte korektně zdůvodnit.
s s
s
s
s
s s
s
s
s s
(Hodnocení 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
3
Písemná zkouška MA010 Grafy: 9.1. 2008, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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). Mějme konečnou množinu uzavřených intervalů na reálné ose. Nad těmito intervaly definujeme graf
následovně: Vrcholy jsou naše intervaly a hrany spojují právě ty dvojice intervalů, které jsou disjunktní.
Grafy definované popsaným způsobem nazvěme mimo-intervalové. (Jsou to vlastně doplňky
lépe známých intervalových grafů.)
a) Podejte zde elementární důkaz faktu, že barevnost mimo-intervalového grafu je vždy rovna
velikosti jeho největší kliky.
b) Popište efektivní algoritmus (počítající v polynomiálním čase) pro určení barevnosti vstupního
mimo-intervalového grafu.
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
4
Písemná zkouška MA010 Grafy: 9.1. 2008, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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í:
Hrany (všechny!) každého jednoduchého neorientovaného grafu G lze zorientovat tak, aby do
každého jeho vrcholu v  V (G) stupně dv přicházelo nejvýše dv/2 šipek. (  je horní celá část.)
Proč analogické tvrzení neplatí s nejvýše dv/2 přicházejícími šipkami?
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
5
Písemná zkouška MA010 Grafy: 9.1. 2008, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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án je následující jednoduchý graf na 10 vrcholech.
s s
s
s
ss
s
s
s s
Vašim úkolem je zjistit, kolik vzájemně neisomorfních grafů může vzniknout z tohoto grafu přidáním
jednoho nového vrcholu x a (jediné) hrany z x do některého původního vrcholu. Svou odpověď aspoň
stručně zdůvodněte.
(Hodnocení 17 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
6
Písemná zkouška MA010 Grafy: 9.1. 2008, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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 11 vrcholech:
s s
s
s
s
s s
s
s
s s
Vašim úkolem je zodpovědět správně následující tř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 nejdelší kružnice v tomto grafu?
s s
s
s
s
s s
s
s
s s
b) Nakreslete libovolný jednoduchý graf, který má stejnou posloupnost stupňů jako zadaný graf
a přitom jej lze obarvit dvěma barvami.
c) Jaká je barevnost našeho grafu? Nazapomeňte korektně zdůvodnit.
s s
s
s
s
s s
s
s
s s
(Hodnocení 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
7
Písemná zkouška MA010 Grafy: 9.1. 2008, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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). Mějme konečnou množinu uzavřených intervalů na reálné ose. Nad těmito intervaly definujeme graf
následovně: Vrcholy jsou naše intervaly a hrany spojují právě ty dvojice intervalů, které jsou disjunktní.
Grafy definované popsaným způsobem nazvěme mimo-intervalové. (Jsou to vlastně doplňky
lépe známých intervalových grafů.)
a) Podejte zde elementární důkaz faktu, že barevnost mimo-intervalového grafu je vždy rovna
velikosti jeho největší kliky.
b) Popište efektivní algoritmus (počítající v polynomiálním čase) pro určení barevnosti vstupního
mimo-intervalového grafu.
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
8
Písemná zkouška MA010 Grafy: 9.1. 2008, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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í:
Hrany (všechny!) každého jednoduchého neorientovaného grafu G lze zorientovat tak, aby do
každého jeho vrcholu v  V (G) stupně dv přicházelo nejvýše dv/2 šipek. (  je horní celá část.)
Proč analogické tvrzení neplatí s nejvýše dv/2 přicházejícími šipkami?
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
9
Písemná zkouška MA010 Grafy: 9.1. 2008, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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án je následující jednoduchý graf na 10 vrcholech.
s s
s
s
ss
s
s
s s
Vašim úkolem je zjistit, kolik vzájemně neisomorfních grafů může vzniknout z tohoto grafu přidáním
jednoho nového vrcholu x a (jediné) hrany z x do některého původního vrcholu. Svou odpověď aspoň
stručně zdůvodněte.
(Hodnocení 17 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
10
Písemná zkouška MA010 Grafy: 9.1. 2008, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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 11 vrcholech:
s s
s
s
s
s s
s
s
s s
Vašim úkolem je zodpovědět správně následující tř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 nejkratší kružnice v tomto grafu?
s s
s
s
s
s s
s
s
s s
b) Nakreslete libovolný jednoduchý graf, který má stejnou posloupnost stupňů jako zadaný graf
a přitom obsahuje dva vrcholy ve vzdálenosti 4 od sebe.
c) Jaká je barevnost našeho grafu? Nazapomeňte korektně zdůvodnit.
s s
s
s
s
s s
s
s
s s
(Hodnocení 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
11
Písemná zkouška MA010 Grafy: 9.1. 2008, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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). Mějme konečnou množinu uzavřených intervalů na reálné ose. Nad těmito intervaly definujeme graf
následovně: Vrcholy jsou naše intervaly a hrany spojují právě ty dvojice intervalů, které jsou disjunktní.
Grafy definované popsaným způsobem nazvěme mimo-intervalové. (Jsou to vlastně doplňky
lépe známých intervalových grafů.)
a) Podejte zde elementární důkaz faktu, že barevnost mimo-intervalového grafu je vždy rovna
velikosti jeho největší kliky.
b) Popište efektivní algoritmus (počítající v polynomiálním čase) pro určení barevnosti vstupního
mimo-intervalového grafu.
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
12
Písemná zkouška MA010 Grafy: 9.1. 2008, var C
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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í:
Hrany (všechny!) každého jednoduchého neorientovaného grafu G lze zorientovat tak, aby do
každého jeho vrcholu v  V (G) stupně dv přicházelo nejvýše dv/2 šipek. (  je horní celá část.)
Proč analogické tvrzení neplatí s nejvýše dv/2 přicházejícími šipkami?
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
13
Písemná zkouška MA010 Grafy: 9.1. 2008, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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án je následující jednoduchý graf na 10 vrcholech.
s s
s
s
ss
s
s
s s
Vašim úkolem je zjistit, kolik vzájemně neisomorfních grafů může vzniknout z tohoto grafu přidáním
jednoho nového vrcholu x a (jediné) hrany z x do některého původního vrcholu. Svou odpověď aspoň
stručně zdůvodněte.
(Hodnocení 17 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
14
Písemná zkouška MA010 Grafy: 9.1. 2008, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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 11 vrcholech:
s s
s
s
s
s s
s
s
s s
Vašim úkolem je zodpovědět správně následující tř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 nejmenší podmnožina X jeho vrcholů taková, že každý jeho vrchol mimo X má
nějakého souseda v X?
s s
s
s
s
s s
s
s
s s
b) Nakreslete libovolný jednoduchý graf, který má stejnou posloupnost stupňů jako zadaný graf
a přitom obsahuje trojúhelník.
c) Jaká je barevnost našeho grafu? Nazapomeňte korektně zdůvodnit.
s s
s
s
s
s s
s
s
s s
(Hodnocení 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
15
Písemná zkouška MA010 Grafy: 9.1. 2008, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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). Mějme konečnou množinu uzavřených intervalů na reálné ose. Nad těmito intervaly definujeme graf
následovně: Vrcholy jsou naše intervaly a hrany spojují právě ty dvojice intervalů, které jsou disjunktní.
Grafy definované popsaným způsobem nazvěme mimo-intervalové. (Jsou to vlastně doplňky
lépe známých intervalových grafů.)
a) Podejte zde elementární důkaz faktu, že barevnost mimo-intervalového grafu je vždy rovna
velikosti jeho největší kliky.
b) Popište efektivní algoritmus (počítající v polynomiálním čase) pro určení barevnosti vstupního
mimo-intervalového grafu.
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
16
Písemná zkouška MA010 Grafy: 9.1. 2008, var D
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte 100 minut, celkem získáte 
17+15+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í:
Hrany (všechny!) každého jednoduchého neorientovaného grafu G lze zorientovat tak, aby do
každého jeho vrcholu v  V (G) stupně dv přicházelo nejvýše dv/2 šipek. (  je horní celá část.)
Proč analogické tvrzení neplatí s nejvýše dv/2 přicházejícími šipkami?
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)