1
Písemný test MA010 Grafy: 11.1. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické 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í tři grafy na 8 vrcholech každý.
A B C
s s
s
s
ss
s
s
s s
s
s
ss
s
s
s s
s
s
ss
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í 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
2
Písemný test MA010 Grafy: 11.1. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické přístroje včetně mobilů. Pracujte samostatně.
Povolen je 1 list A4 vlastnoručně psaných
poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2). Pro následující graf na 11 vrcholech odpovězte níže uvedené tři otázky. Vaše řešení vyznačte vždy
do příslušné kopie obrázku grafu níže. V případě existence více řešení vyznačte libovolné.
Navíc u každé otázky stručně (alespoň neformálně) zdůvodněte správnost vašeho řešení (tj.
například proč je vaše množina největší / nejmenší. . . ).
s s s
s
s
sss
s
s
s
a) Určete barevnost tohoto grafu a vyznačte příslušné obarvení.
s s s
s
s
sss
s
s
s
b) Určete velikost největší nezávislé množiny v tomto grafu a vyznačte ji (zakroužkováním vrcholů).
s s s
s
s
sss
s
s
s
c) Určete velikost nejmenší dominující množiny v tomto grafu a vyznačte ji. (Dominující množina
vrcholů je taková, že každý jiný vrchol grafu s některým jejím vrcholem sousedí.)
s s s
s
s
sss
s
s
s
(Hodnocení 25 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
3
Písemný test MA010 Grafy: 11.1. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické 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ě 2007 koster a přitom neobsahuje jako
podgraf kružnici délky 2007. Nezbytnou součástí řešení je i zdůvodnění, proč váš graf má 2007 koster.
(Mohlo by se vám hodit, že 2007 = 9  223.)
(Hodnocení 10 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
4
Písemný test MA010 Grafy: 11.1. 2007, var A
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické přístroje včetně mobilů. Pracujte samostatně.
Povolen je 1 list A4 vlastnoručně psaných
poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4). Jak jistě víte, Kn,n je úplný bipartitní graf na n a n vrcholech. Označme dále Kˇ
n,n graf vzniklý z
Kn,n podrozdělením jedné jeho hrany jedním novým vrcholem (stupně 2). Pokud označíme jako A
počet všech koster grafu Kn,n a jako B počet všech koster Kˇ
n,n, tak platí vztah
B = 1 +
n - 1
n
2
 A .
Dokažte.
(Návod: nemusíte spočítat hodnoty A, B, abyste vztah dokázali. . . )
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
5
Písemný test MA010 Grafy: 11.1. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické 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í tři grafy na 8 vrcholech každý.
A B C
s s
s
s
ss
s
s
s s
s
s
ss
s
s
s s
s
s
ss
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í 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
6
Písemný test MA010 Grafy: 11.1. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické přístroje včetně mobilů. Pracujte samostatně.
Povolen je 1 list A4 vlastnoručně psaných
poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2). Pro následující graf na 11 vrcholech odpovězte níže uvedené tři otázky. Vaše řešení vyznačte vždy
do příslušné kopie obrázku grafu níže. V případě existence více řešení vyznačte libovolné.
Navíc u každé otázky stručně (alespoň neformálně) zdůvodněte správnost vašeho řešení (tj.
například proč je vaše množina největší / nejmenší. . . ).
s s s
s
s
sss
s
s
s
a) Určete barevnost tohoto grafu a vyznačte příslušné obarvení.
s s s
s
s
sss
s
s
s
b) Určete velikost největší nezávislé množiny v tomto grafu a vyznačte ji (zakroužkováním vrcholů).
s s s
s
s
sss
s
s
s
c) Určete velikost nejmenší dominující množiny v tomto grafu a vyznačte ji. (Dominující množina
vrcholů je taková, že každý jiný vrchol grafu s některým jejím vrcholem sousedí.)
s s s
s
s
sss
s
s
s
(Hodnocení 25 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
7
Písemný test MA010 Grafy: 11.1. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické 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ě 2006 koster a přitom neobsahuje jako
podgraf kružnici délky 2006. Nezbytnou součástí řešení je i zdůvodnění, proč váš graf má 2006 koster.
(Mohlo by se vám hodit, že 2006 = 34  59.)
(Hodnocení 10 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
8
Písemný test MA010 Grafy: 11.1. 2007, var B
Identifikace
UČO:
JMÉNO:
Poloha v místnosti:
Na vypracování máte ve dvou částech(!) 60+60 minut,
celkem získáte  40 + 30 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é elektronické přístroje včetně mobilů. Pracujte samostatně.
Povolen je 1 list A4 vlastnoručně psaných
poznámek k předmětu.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4). Jak jistě víte, Kn,n je úplný bipartitní graf na n a n vrcholech. Označme dále Kˇ
n,n graf vzniklý z
Kn,n podrozdělením jedné jeho hrany jedním novým vrcholem (stupně 2). Pokud označíme jako A
počet všech koster grafu Kn,n a jako B počet všech koster Kˇ
n,n, tak platí vztah
B = 1 +
n - 1
n
2
 A .
Dokažte.
(Návod: nemusíte spočítat hodnoty A, B, abyste vztah dokázali. . . )
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)