1
Písemný test MA010 Grafy: 17.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). Vašim úkolem je sestrojit všechny neisomorfní jednoduché souvislé grafy na 6 vrcholech mající posloupnost
stupňů
1, 2, 2, 2, 2, 3 .
Zároveň zdůvodněte, proč vaše grafy jsou vzájemně neisomorfní a proč jsou všechny.
(Hodnocení 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
2
Písemný test MA010 Grafy: 17.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 velikost největšího párování v tomto grafu a vyznačte jej (obtáhněte jeho hrany).
s s s
s
s
sss
s
s
s
b) Určete velikost největší kliky (úplného podgrafu) 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šího vrcholového pokrytí v tomto grafu a vyznačte jej. (Vrcholové pokrytí
je množina vrcholů taková, že každá hrana grafu je incidentní s některým jejím vrcholem.)
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: 17.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). Graf G je perfektní, pokud v každém jeho indukovaném podgrafu F platí, že barevnost F je rovna
velikosti největší kliky (úplného podgrafu) v F.
Nechť graf G (intervalový) je určen množinou intervalů I1, I2, . . . , In na přímce následovně: Vrcholy
G jsou právě intervaly I1, I2, . . . , In a hrany tvoří dvojice intervalů, které mají neprázdný průnik.
Dokažte, že G je perfektní graf.
(Návod: pro zjednodušení si všimněte, že indukovaný podgraf intervalového grafu G je taktéž
intervalový ­ určený příslušnou podmnožinou intervalů.)
(Hodnocení 10 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
4
Písemný test MA010 Grafy: 17.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). Nechť graf H má následující vlastnost: V H existují dvě kliky (úplné podgrafy), které ve sjednocení
obsahují všechny vrcholy H. Dokažte, že pak je graf H perfektní.
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
5
Písemný test MA010 Grafy: 17.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). Vašim úkolem je sestrojit všechny neisomorfní jednoduché souvislé grafy na 6 vrcholech mající posloupnost
stupňů
2, 2, 2, 2, 3, 3 .
Zároveň zdůvodněte, proč vaše grafy jsou vzájemně neisomorfní a proč jsou všechny.
(Hodnocení 15 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
6
Písemný test MA010 Grafy: 17.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 velikost největšího párování v tomto grafu a vyznačte jej (obtáhněte jeho hrany).
s s s
s
s
sss
s
s
s
b) Určete velikost největší kliky (úplného podgrafu) 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šího vrcholového pokrytí v tomto grafu a vyznačte jej. (Vrcholové pokrytí
je množina vrcholů taková, že každá hrana grafu je incidentní s některým jejím vrcholem.)
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: 17.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). Graf G je perfektní, pokud v každém jeho indukovaném podgrafu F platí, že barevnost F je rovna
velikosti největší kliky (úplného podgrafu) v F.
Nechť graf G (intervalový) je určen množinou intervalů I1, I2, . . . , In na přímce následovně: Vrcholy
G jsou právě intervaly I1, I2, . . . , In a hrany tvoří dvojice intervalů, které mají neprázdný průnik.
Dokažte, že G je perfektní graf.
(Návod: pro zjednodušení si všimněte, že indukovaný podgraf intervalového grafu G je taktéž
intervalový ­ určený příslušnou podmnožinou intervalů.)
(Hodnocení 10 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)
8
Písemný test MA010 Grafy: 17.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). Nechť graf H má následující vlastnost: V H existují dvě kliky (úplné podgrafy), které ve sjednocení
obsahují všechny vrcholy H. Dokažte, že pak je graf H perfektní.
(Hodnocení 20 bodů. Pište řešení přímo k zadání na stejný(!) list papíru.)