1
Řešení zkoušky 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.
Vzorové výsledky (řešení):
Správná odpověď je A  D a B  C. Tuto odpověď je však nutno správně zdůvodnit. To
znamená v případě isomorfních dvojic nalézt jejich isomorfismus (s tím obvykle nebyly problémy).
V případě neisomorfních dvojic bylo třeba rozdíl zdůvodnit nějakými rozdíly mezi dotyčnými grafy,
například kdy jeden z nich obsahuje kružnice lichých délek a druhý ne, nebo kdy obsahují rozdílné
počty kopií nějakých malých podgrafů.
Mimo případů, kdy isomorfní dvojice byly určené špatně, nejčastější chybou bylo nezdůvodnění
neisomorfních dvojic nebo případně chybné zdůvodnění. Například vůbec nestačí napsat, že dva
grafy obsahují rozdílné počty C4, musíte napsat i kolik a které. Dalším příkladem častých chyb je,
když jste počty podgrafů jako třeba C4 určili špatně, pak celá následná argumentace padá na hlavu.
Takže pokud vám připadá, že jste dostali příliš málo bodů za "správné" řešení, tak je to právě kvůli
výše uvedeným chybám.
2
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?
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
Vzorové výsledky (řešení):
a) Největší nezávislá množina má velikost 4. Pozor však, k úplné odpovědi musíte kromě vyznačení
této množiny přidat i stručné zdůvodnění, proč větší být nemůže. To lze třeba krátkým (a inteligentním)
rozborem možostí, nebo nějakým jiným chytrým pozorováním, třeba pokrytím všech vrcholů
(nejlépe) lichými kružnicemi.
b) Těchto podgrafů je 12. Zde je potřeba systematický přístup k jejich nalezení s využitím symetrií
grafu, případně dobré zdůvodnění jejich neexistence. Pokud byla systematičnost v řešení vidět, již
nebylo vyžadováno i zdůvodnění správnosti.
c) Těchto podgrafů je 10. Zde je opět potřeba především systematický přístup k jejich nalezení s
využitím symetrií grafu. V této podotázce bohužel většina chybovala (ve všech variantách příkladu).
Zkuste si to propočíst znovu!
d) Nejdelší kružnice je délky 9. Nalézt takovou určitě není obtížné a skoro každý to měl správně,
ale jen málokomu se podařilo i zdůvodnit (ve variantě s 9), že delší kružnice není. Na tom se také
ztrácelo.
Takže opět, pokud vám připadá, že jste dostali příliš málo bodů i za "správné" řešení, tak je to
právě kvůli chybícím zdůvodněním odpovědí.
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.)
Vzorové výsledky (řešení):
Jeden možný přístup vedoucí k řešení je následovný: Sestrojíme graf G ze dvou kružnic délek a a b
sdílejících k po sobě jdoucích hran. Pak počet koster G je ab - k2. Vhodné celočíselné řešení rovnice
ab - k2 = 2017 najdeme například pro k = 2, a = 43 a b = 47, nebo k = 4, a = 19 a b = 107.
Jiný přístup (bez tak velkých prvočísel) je třeba tento: Sestrojíme graf H ze tří kružnic délek a,
b a c sdílejících jednu společnou hranu. Počet koster H je abc - a - b - c + 2, jak není těžké přímo
spočítat. Neboli potřebujeme vyřešit celočíselnou rovnici abc-a-b-c+2 = 2017. Pro jednoduchost
zvolme c = 3, tudíž 3ab-a-b-1 = 2017, a další úpravou na součin na levé straně (to je standardní
postup hledání celočíselných řešení) po vynásobení 3 získáme (3a - 1)(3b - 1) = 3  2017 + 4 = 6055.
Zde už je rozklad na součin poměrně jednoduchý 6055 = 5  7  173. Z toho hned získáme a = 12 a
b = 58. Další možnosti samozřejmě také existují. . .
3
Bohužel se tento příklad ukázal jako náročnější, než bylo zamýšleno. Podle následné diskuse v IS by
to vypadalo, jako že nepřekonatelným problémem byl výskyt velkých (prvo)čísel v řešení, ale pohled
do odevzdaných listů ukazuje, že hlavní zádrhel byl ve lpění na stereotypech řešení převzatých
z loňských obdobných příkladů. Zadání tohoto příkladu bylo záměrně navrženo tak, aby přístup
"kružnice s jednou tětivou" (u kterého zůstala většina ze studentů) k řešení prostě vést nemohl! To
ostatně naznačila i poznámka o prvočíselnosti 1009. Proto místo marných pokusů o dělení prvočísla
bylo třeba jen zkusit něco jiného. . . (Ostatně celá matematika je o hledání nových přístupů.)
Kdo se dostal na některou slibnou cestu k řešení (a pěkně to napsal, aby to bylo vidět), dostal už
docela hodně bodů, třebaže konkrétní celočíselné řešení nenalezl. Kdo aspoň obecně rozebral přístup
s kružnicí s jednou tětivou a došel viditelně k poznání, že tudy cesta nevede, také pár bodů obdržel.
Pokusy chybně počítající počty koster nebo využívající kružnice necelých délek bodovány nebyly.
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. . . )
Vzorové výsledky (řešení):
Toto je skutečně obtížný příklad, i když správné řešení je docela krátké. Nechť G je tedy 8regulární
graf. Pak G je nakreslitelný jedním uzavřeným tahem sudé délky, ze kterého vybereme
každou druhou hranu. Tím dostaneme 4-regulární podgraf G. Tentýž postup opakujeme s každou
souvislou komponentou G a dostaneme tak nakonec 2-regulární podgraf G se stejnou množinou
vrcholů jako G. Nakonec stačí z G odebrat všechny hrany G a vyjde 6-regulární podgraf v G.
Že tento příklad nebyl neřešitelný, ukazuje jedno zcela správné řešení. Na myšlenku odebrat z G
nějaký jeho 2-regulární podgraf přišlo dost z vás, ale chybně k tomu chtělo využít Hamiltonovskou
kružnici, která prostě nemusí existovat. Přesto za tuto myšlenku bylo uděleno pár bodů. Jiné pokusy
snažící se nějak přímo vybrat z každého vrcholu 6 jeho hran bohužel k ničemu nevedou a nebyly
hodnoceny vůbec.
4
Řešení zkoušky 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.
Vzorové výsledky (řešení):
Správná odpověď je C  D. Tuto odpověď je však nutno správně zdůvodnit. To znamená v
případě isomorfních dvojic nalézt jejich isomorfismus (s tím obvykle nebyly problémy). V případě
neisomorfních dvojic bylo třeba rozdíl zdůvodnit nějakými rozdíly mezi dotyčnými grafy, například
kdy jeden z nich obsahuje kružnice lichých délek a druhý ne, nebo kdy obsahují rozdílné počty kopií
nějakých malých podgrafů.
Mimo případů, kdy isomorfní dvojice byly určené špatně, nejčastější chybou bylo nezdůvodnění
neisomorfních dvojic nebo případně chybné zdůvodnění. Například vůbec nestačí napsat, že dva
grafy obsahují rozdílné počty C4, musíte napsat i kolik a které. Dalším příkladem častých chyb je,
když jste počty podgrafů jako třeba C4 určili špatně, pak celá následná argumentace padá na hlavu.
Takže pokud vám připadá, že jste dostali příliš málo bodů za "správné" řešení, tak je to právě kvůli
výše uvedeným chybám.
5
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?
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
Vzorové výsledky (řešení):
a) Největší nezávislá množina má velikost 5. Pozor však, k úplné odpovědi musíte kromě vyznačení
této množiny přidat i stručné zdůvodnění, proč větší být nemůže. To lze třeba krátkým (a inteligentním)
rozborem možostí, nebo nějakým jiným chytrým pozorováním, třeba pokrytím všech vrcholů
(nejlépe) lichými kružnicemi.
b) Těchto podgrafů je 0. Zde je potřeba systematický přístup k jejich nalezení s využitím symetrií
grafu, případně dobré zdůvodnění jejich neexistence. Pokud byla systematičnost v řešení vidět, již
nebylo vyžadováno i zdůvodnění správnosti.
c) Těchto podgrafů je 15. Zde je opět potřeba především systematický přístup k jejich nalezení s
využitím symetrií grafu. V této podotázce bohužel většina chybovala (ve všech variantách příkladu).
Zkuste si to propočíst znovu!
d) Nejdelší kružnice je délky 10. Nalézt takovou určitě není obtížné a skoro každý to měl správně,
ale jen málokomu se podařilo i zdůvodnit (ve variantě s 9), že delší kružnice není. Na tom se také
ztrácelo.
Takže opět, pokud vám připadá, že jste dostali příliš málo bodů i za "správné" řešení, tak je to
právě kvůli chybícím zdůvodněním odpovědí.
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.)
Vzorové výsledky (řešení):
Jeden možný přístup vedoucí k řešení je následovný: Sestrojíme graf G ze dvou kružnic délek a a b
sdílejících k po sobě jdoucích hran. Pak počet koster G je ab - k2. Vhodné celočíselné řešení rovnice
ab - k2 = 2017 najdeme například pro k = 2, a = 43 a b = 47, nebo k = 4, a = 19 a b = 107.
Jiný přístup (bez tak velkých prvočísel) je třeba tento: Sestrojíme graf H ze tří kružnic délek a,
b a c sdílejících jednu společnou hranu. Počet koster H je abc - a - b - c + 2, jak není těžké přímo
spočítat. Neboli potřebujeme vyřešit celočíselnou rovnici abc-a-b-c+2 = 2017. Pro jednoduchost
zvolme c = 3, tudíž 3ab-a-b-1 = 2017, a další úpravou na součin na levé straně (to je standardní
postup hledání celočíselných řešení) po vynásobení 3 získáme (3a - 1)(3b - 1) = 3  2017 + 4 = 6055.
Zde už je rozklad na součin poměrně jednoduchý 6055 = 5  7  173. Z toho hned získáme a = 12 a
b = 58. Další možnosti samozřejmě také existují. . .
6
Bohužel se tento příklad ukázal jako náročnější, než bylo zamýšleno. Podle následné diskuse v IS by
to vypadalo, jako že nepřekonatelným problémem byl výskyt velkých (prvo)čísel v řešení, ale pohled
do odevzdaných listů ukazuje, že hlavní zádrhel byl ve lpění na stereotypech řešení převzatých
z loňských obdobných příkladů. Zadání tohoto příkladu bylo záměrně navrženo tak, aby přístup
"kružnice s jednou tětivou" (u kterého zůstala většina ze studentů) k řešení prostě vést nemohl! To
ostatně naznačila i poznámka o prvočíselnosti 1009. Proto místo marných pokusů o dělení prvočísla
bylo třeba jen zkusit něco jiného. . . (Ostatně celá matematika je o hledání nových přístupů.)
Kdo se dostal na některou slibnou cestu k řešení (a pěkně to napsal, aby to bylo vidět), dostal už
docela hodně bodů, třebaže konkrétní celočíselné řešení nenalezl. Kdo aspoň obecně rozebral přístup
s kružnicí s jednou tětivou a došel viditelně k poznání, že tudy cesta nevede, také pár bodů obdržel.
Pokusy chybně počítající počty koster nebo využívající kružnice necelých délek bodovány nebyly.
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. . . )
Vzorové výsledky (řešení):
Toto je skutečně obtížný příklad, i když správné řešení je docela krátké. Nechť G je tedy 8regulární
graf. Pak G je nakreslitelný jedním uzavřeným tahem sudé délky, ze kterého vybereme
každou druhou hranu. Tím dostaneme 4-regulární podgraf G. Tentýž postup opakujeme s každou
souvislou komponentou G a dostaneme tak nakonec 2-regulární podgraf G se stejnou množinou
vrcholů jako G. Nakonec stačí z G odebrat všechny hrany G a vyjde 6-regulární podgraf v G.
Že tento příklad nebyl neřešitelný, ukazuje jedno zcela správné řešení. Na myšlenku odebrat z G
nějaký jeho 2-regulární podgraf přišlo dost z vás, ale chybně k tomu chtělo využít Hamiltonovskou
kružnici, která prostě nemusí existovat. Přesto za tuto myšlenku bylo uděleno pár bodů. Jiné pokusy
snažící se nějak přímo vybrat z každého vrcholu 6 jeho hran bohužel k ničemu nevedou a nebyly
hodnoceny vůbec.
7
Řešení zkoušky 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.
Vzorové výsledky (řešení):
Správná odpověď je A  C. Tuto odpověď je však nutno správně zdůvodnit. To znamená v
případě isomorfních dvojic nalézt jejich isomorfismus (s tím obvykle nebyly problémy). V případě
neisomorfních dvojic bylo třeba rozdíl zdůvodnit nějakými rozdíly mezi dotyčnými grafy, například
kdy jeden z nich obsahuje kružnice lichých délek a druhý ne, nebo kdy obsahují rozdílné počty kopií
nějakých malých podgrafů.
Mimo případů, kdy isomorfní dvojice byly určené špatně, nejčastější chybou bylo nezdůvodnění
neisomorfních dvojic nebo případně chybné zdůvodnění. Například vůbec nestačí napsat, že dva
grafy obsahují rozdílné počty C4, musíte napsat i kolik a které. Dalším příkladem častých chyb je,
když jste počty podgrafů jako třeba C4 určili špatně, pak celá následná argumentace padá na hlavu.
Takže pokud vám připadá, že jste dostali příliš málo bodů za "správné" řešení, tak je to právě kvůli
výše uvedeným chybám.
8
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?
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
Vzorové výsledky (řešení):
a) Největší nezávislá množina má velikost 4. Pozor však, k úplné odpovědi musíte kromě vyznačení
této množiny přidat i stručné zdůvodnění, proč větší být nemůže. To lze třeba krátkým (a inteligentním)
rozborem možostí, nebo nějakým jiným chytrým pozorováním, třeba pokrytím všech vrcholů
(nejlépe) lichými kružnicemi.
b) Těchto podgrafů je 12. Zde je potřeba systematický přístup k jejich nalezení s využitím symetrií
grafu, případně dobré zdůvodnění jejich neexistence. Pokud byla systematičnost v řešení vidět, již
nebylo vyžadováno i zdůvodnění správnosti.
c) Těchto podgrafů je 10. Zde je opět potřeba především systematický přístup k jejich nalezení s
využitím symetrií grafu. V této podotázce bohužel většina chybovala (ve všech variantách příkladu).
Zkuste si to propočíst znovu!
d) Nejdelší kružnice je délky 9. Nalézt takovou určitě není obtížné a skoro každý to měl správně,
ale jen málokomu se podařilo i zdůvodnit (ve variantě s 9), že delší kružnice není. Na tom se také
ztrácelo.
Takže opět, pokud vám připadá, že jste dostali příliš málo bodů i za "správné" řešení, tak je to
právě kvůli chybícím zdůvodněním odpovědí.
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.)
Vzorové výsledky (řešení):
Jeden možný přístup vedoucí k řešení je následovný: Sestrojíme graf G ze dvou kružnic délek a a b
sdílejících k po sobě jdoucích hran. Pak počet koster G je ab - k2. Vhodné celočíselné řešení rovnice
ab - k2 = 2017 najdeme například pro k = 2, a = 43 a b = 47, nebo k = 4, a = 19 a b = 107.
Jiný přístup (bez tak velkých prvočísel) je třeba tento: Sestrojíme graf H ze tří kružnic délek a,
b a c sdílejících jednu společnou hranu. Počet koster H je abc - a - b - c + 2, jak není těžké přímo
spočítat. Neboli potřebujeme vyřešit celočíselnou rovnici abc-a-b-c+2 = 2017. Pro jednoduchost
zvolme c = 3, tudíž 3ab-a-b-1 = 2017, a další úpravou na součin na levé straně (to je standardní
postup hledání celočíselných řešení) po vynásobení 3 získáme (3a - 1)(3b - 1) = 3  2017 + 4 = 6055.
Zde už je rozklad na součin poměrně jednoduchý 6055 = 5  7  173. Z toho hned získáme a = 12 a
b = 58. Další možnosti samozřejmě také existují. . .
9
Bohužel se tento příklad ukázal jako náročnější, než bylo zamýšleno. Podle následné diskuse v IS by
to vypadalo, jako že nepřekonatelným problémem byl výskyt velkých (prvo)čísel v řešení, ale pohled
do odevzdaných listů ukazuje, že hlavní zádrhel byl ve lpění na stereotypech řešení převzatých
z loňských obdobných příkladů. Zadání tohoto příkladu bylo záměrně navrženo tak, aby přístup
"kružnice s jednou tětivou" (u kterého zůstala většina ze studentů) k řešení prostě vést nemohl! To
ostatně naznačila i poznámka o prvočíselnosti 1009. Proto místo marných pokusů o dělení prvočísla
bylo třeba jen zkusit něco jiného. . . (Ostatně celá matematika je o hledání nových přístupů.)
Kdo se dostal na některou slibnou cestu k řešení (a pěkně to napsal, aby to bylo vidět), dostal už
docela hodně bodů, třebaže konkrétní celočíselné řešení nenalezl. Kdo aspoň obecně rozebral přístup
s kružnicí s jednou tětivou a došel viditelně k poznání, že tudy cesta nevede, také pár bodů obdržel.
Pokusy chybně počítající počty koster nebo využívající kružnice necelých délek bodovány nebyly.
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. . . )
Vzorové výsledky (řešení):
Toto je skutečně obtížný příklad, i když správné řešení je docela krátké. Nechť G je tedy 8regulární
graf. Pak G je nakreslitelný jedním uzavřeným tahem sudé délky, ze kterého vybereme
každou druhou hranu. Tím dostaneme 4-regulární podgraf G. Tentýž postup opakujeme s každou
souvislou komponentou G a dostaneme tak nakonec 2-regulární podgraf G se stejnou množinou
vrcholů jako G. Nakonec stačí z G odebrat všechny hrany G a vyjde 6-regulární podgraf v G.
Že tento příklad nebyl neřešitelný, ukazuje jedno zcela správné řešení. Na myšlenku odebrat z G
nějaký jeho 2-regulární podgraf přišlo dost z vás, ale chybně k tomu chtělo využít Hamiltonovskou
kružnici, která prostě nemusí existovat. Přesto za tuto myšlenku bylo uděleno pár bodů. Jiné pokusy
snažící se nějak přímo vybrat z každého vrcholu 6 jeho hran bohužel k ničemu nevedou a nebyly
hodnoceny vůbec.
10
Řešení zkoušky 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.
Vzorové výsledky (řešení):
Správná odpověď je B  D. Tuto odpověď je však nutno správně zdůvodnit. To znamená v
případě isomorfních dvojic nalézt jejich isomorfismus (s tím obvykle nebyly problémy). V případě
neisomorfních dvojic bylo třeba rozdíl zdůvodnit nějakými rozdíly mezi dotyčnými grafy, například
kdy jeden z nich obsahuje kružnice lichých délek a druhý ne, nebo kdy obsahují rozdílné počty kopií
nějakých malých podgrafů.
Mimo případů, kdy isomorfní dvojice byly určené špatně, nejčastější chybou bylo nezdůvodnění
neisomorfních dvojic nebo případně chybné zdůvodnění. Například vůbec nestačí napsat, že dva
grafy obsahují rozdílné počty C4, musíte napsat i kolik a které. Dalším příkladem častých chyb je,
když jste počty podgrafů jako třeba C4 určili špatně, pak celá následná argumentace padá na hlavu.
Takže pokud vám připadá, že jste dostali příliš málo bodů za "správné" řešení, tak je to právě kvůli
výše uvedeným chybám.
11
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?
b) Kolik náš graf obsahuje podgrafů isomorfních kružnici C5?
c) Kolik náš graf obsahuje podgrafů isomorfních kružnici C6?
d) Jakou nejdelší kružnici náš graf obsahuje jako podgraf?
Vzorové výsledky (řešení):
a) Největší nezávislá množina má velikost 4. Pozor však, k úplné odpovědi musíte kromě vyznačení
této množiny přidat i stručné zdůvodnění, proč větší být nemůže. To lze třeba krátkým (a inteligentním)
rozborem možostí, nebo nějakým jiným chytrým pozorováním, třeba pokrytím všech vrcholů
(nejlépe) lichými kružnicemi.
b) Těchto podgrafů je 6. Zde je potřeba systematický přístup k jejich nalezení s využitím symetrií
grafu, případně dobré zdůvodnění jejich neexistence. Pokud byla systematičnost v řešení vidět, již
nebylo vyžadováno i zdůvodnění správnosti.
c) Těchto podgrafů je 7. Zde je opět potřeba především systematický přístup k jejich nalezení s
využitím symetrií grafu. V této podotázce bohužel většina chybovala (ve všech variantách příkladu).
Zkuste si to propočíst znovu!
d) Nejdelší kružnice je délky 10. Nalézt takovou určitě není obtížné a skoro každý to měl správně,
ale jen málokomu se podařilo i zdůvodnit (ve variantě s 9), že delší kružnice není. Na tom se také
ztrácelo.
Takže opět, pokud vám připadá, že jste dostali příliš málo bodů i za "správné" řešení, tak je to
právě kvůli chybícím zdůvodněním odpovědí.
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.)
Vzorové výsledky (řešení):
Jeden možný přístup vedoucí k řešení je následovný: Sestrojíme graf G ze dvou kružnic délek a a b
sdílejících k po sobě jdoucích hran. Pak počet koster G je ab - k2. Vhodné celočíselné řešení rovnice
ab - k2 = 2017 najdeme například pro k = 2, a = 43 a b = 47, nebo k = 4, a = 19 a b = 107.
Jiný přístup (bez tak velkých prvočísel) je třeba tento: Sestrojíme graf H ze tří kružnic délek a,
b a c sdílejících jednu společnou hranu. Počet koster H je abc - a - b - c + 2, jak není těžké přímo
spočítat. Neboli potřebujeme vyřešit celočíselnou rovnici abc-a-b-c+2 = 2017. Pro jednoduchost
zvolme c = 3, tudíž 3ab-a-b-1 = 2017, a další úpravou na součin na levé straně (to je standardní
postup hledání celočíselných řešení) po vynásobení 3 získáme (3a - 1)(3b - 1) = 3  2017 + 4 = 6055.
Zde už je rozklad na součin poměrně jednoduchý 6055 = 5  7  173. Z toho hned získáme a = 12 a
b = 58. Další možnosti samozřejmě také existují. . .
12
Bohužel se tento příklad ukázal jako náročnější, než bylo zamýšleno. Podle následné diskuse v IS by
to vypadalo, jako že nepřekonatelným problémem byl výskyt velkých (prvo)čísel v řešení, ale pohled
do odevzdaných listů ukazuje, že hlavní zádrhel byl ve lpění na stereotypech řešení převzatých
z loňských obdobných příkladů. Zadání tohoto příkladu bylo záměrně navrženo tak, aby přístup
"kružnice s jednou tětivou" (u kterého zůstala většina ze studentů) k řešení prostě vést nemohl! To
ostatně naznačila i poznámka o prvočíselnosti 1009. Proto místo marných pokusů o dělení prvočísla
bylo třeba jen zkusit něco jiného. . . (Ostatně celá matematika je o hledání nových přístupů.)
Kdo se dostal na některou slibnou cestu k řešení (a pěkně to napsal, aby to bylo vidět), dostal už
docela hodně bodů, třebaže konkrétní celočíselné řešení nenalezl. Kdo aspoň obecně rozebral přístup
s kružnicí s jednou tětivou a došel viditelně k poznání, že tudy cesta nevede, také pár bodů obdržel.
Pokusy chybně počítající počty koster nebo využívající kružnice necelých délek bodovány nebyly.
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. . . )
Vzorové výsledky (řešení):
Toto je skutečně obtížný příklad, i když správné řešení je docela krátké. Nechť G je tedy 8regulární
graf. Pak G je nakreslitelný jedním uzavřeným tahem sudé délky, ze kterého vybereme
každou druhou hranu. Tím dostaneme 4-regulární podgraf G. Tentýž postup opakujeme s každou
souvislou komponentou G a dostaneme tak nakonec 2-regulární podgraf G se stejnou množinou
vrcholů jako G. Nakonec stačí z G odebrat všechny hrany G a vyjde 6-regulární podgraf v G.
Že tento příklad nebyl neřešitelný, ukazuje jedno zcela správné řešení. Na myšlenku odebrat z G
nějaký jeho 2-regulární podgraf přišlo dost z vás, ale chybně k tomu chtělo využít Hamiltonovskou
kružnici, která prostě nemusí existovat. Přesto za tuto myšlenku bylo uděleno pár bodů. Jiné pokusy
snažící se nějak přímo vybrat z každého vrcholu 6 jeho hran bohužel k ničemu nevedou a nebyly
hodnoceny vůbec.