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.
Vzorové výsledky (řešení):
Výsledem je 4 vzájemně neisomorfních grafů. Valná většina z vás správně odhalila, že záleží jedině
na tom, kolik "nesymetrických" vrcholů nakreslený graf obsahuje. Přesně řečeno, kolik je vrcholových
orbit grupy automorfismů.
Přitom ve variantách B,D bylo poměrně snadnější ty správné symetrie nalézt, ale jen málokdo
se vyrovnal i s požadavkem zdůvodnění, tedy vysvětlit i proč další symetrie nejsou. (To byl častý
důvod ztráty bodů i při správně určeném počtu.)
Ve variantách A,C bylo více symetrií k objevení, které jen někteří našli a ostatní pak většinou měli
odpovědi jako 5 nebo 6 získané z objevení té snadnější (zrcadlové) symetrie. Pokud však postup byl
správně systematický a jedinou chybou bylo neobjevení té dodatečné "skryté" symetrie, uděloval
jsem také dost hodně bodů. (Podívejte se na svůj příklad znovu. . . )
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).
2
a) Jak velká je jeho největší nezávislá množina?
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.
Vzorové výsledky (řešení):
a) Jeho největší nezávislá množina má 5 vrcholů (kolem středového).
b) S nakreslením požadovaného grafu nebyl obvykle problém.
c) Barevnost grafu je 4, obarvení není obtížné. Potěšili jste mě, že většina i správně zdůvodnila,
proč graf nelze obarvit 3 barvami: Vnější C5 vyžaduje 3 barvy a až na symetrii je takové obarvení
jednoznačné (to je klíčové). Pak vrcholy kolem středového také dostanou 3 různé barvy, jak lze
zdůvodnit z obrázku, a prostřední vrchol už čtvrtou barvu vyžaduje.
Za každou část bylo po 5 bodů, přičemž hlavním důvodem ubírání bodů bylo nedostatečné zdůvodnění
tam, kde bylo potřeba. Jelikož se varianta B ukázala znatelně obtížnější, všichni její účastnící
obdrželi +1 bod navíc.
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 mimointervalového
grafu.
Vzorové výsledky (řešení):
Dá se říci, že nikdo část a) správně neudělal. Pokusy barvit vrcholy od nejvyšších stupňů a podobně
jsou předem odsouzeny k nezdaru, neboť problém barevnosti je NP-úplný. Aby byl váš postup barvení
použitelný, musí podstatným způsobem využívat strukturu dané intervalové reprezentace. Bohužel
však ani pozorování, že každý další vrchol x mimo největší kliku je s některým vrcholem v kliky
nespojený k ničemu nevede, neboť i když x obarvíme stejnou barvou jako v, takových x může být
více a některé z nich budou jako intervaly disjunktní, tudíž nemůžete všem přiřadit stejnou barvu!
Správným přístupem bylo nejprve udělat algoritmus pro část b). To se některým povedlo velmi
pěkně. Opět však bylo mnoho pokusů snažících se prohledávat kliky nebo barvit hladově podle
stupňů vrcholů, které byly předem odsouzeny k nezdaru (opět je důvodem NP-úplnost problémů
barevnosti i kliky).
Správný barvící algoritmus je následovný:
 Intervaly si seřadíme podle začátků zleva. Štětec si namočíme do barvy 1.
 Mějme štětec namočený barvou c. Postupujeme směrem doprava. Dokud objevujeme jen nové
začátky intervalů, barvíme je všechny barvou c.
 Jakmile narazíme na konec některého intervalu barvy c (intervalů barev < c si nevšímáme),
barvu si změníme na c + 1 a pokračujeme předchozím.
Snadnou analýzou tohoto algoritmu nejen ukážeme jeho korektnost, ale také vidíme, že posloupnost
vybraných intervalů, po kterých jsme měnili barvy, tvoří kliku, takže počet použitých barev je roven
velikosti největší kliky.
Studenti mířící neperspektivními směry jsem odměňoval drobnými pár body, vyšší bodování dostávali
nakonec jen ti, kteří se aspoň přiblížili k podání výše uvedeného algoritmu. Ovšem pozor,
byly mnohé marné pokusy o algoritmus, které na první pohled mohou vypadat podobně, ale jejich
společnou chybou bylo, že barvu 1 používali pro všechny další intervaly překrývající se s prvním. To
samozřejmě nelze, ty další intervaly mohou být mezi sebou disjunktní. Klíčovou myšlenkou postupu
je, že k další barvě musíme přejít, jakmile některý interval první skončí, a pokud u vás tato myšlenka
není obsažena, body za takový pokus nebudou.
3
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?
Vzorové výsledky (řešení):
Nejprve se podíváme na druhou otázku za 5 bodů, kterou skoro každý zvládl. Stačí se podívat na
graf K2 se stupni 1, do každého jeho vrcholu by muselo přicházet 0 hran, což nelze.
Hlavní otázka už dopadala hůře. Někteří se k ní snažili přistupovat přes kreslení grafu jedním
tahem a zorientování tohoto tahu, ale dělalo jim problém se vyrovnat s vrcholy lichých stupňů. Jiní
zkoušeli důkaz indukcí přes počet vrcholů, ale těm se vůbec nepovedl indukční krok, takže takové
pokusy byly neuznatelné. Dá se to i tak, ale pro indukční předpoklad se musí hrany přidávaného
vrcholu vhodně "přemostit".
Nejhezčí řešení vymyslelo pár studentů, kteří si všimli významné role zorientovaných kružnic.
(Bohužel nikdo z nich ani toto hezké řešení nedotáhl do formálně správného důkazu.) Formálně
postupujeme indukcí podle počtu kružnic či počtu hran grafu. Stromy zorientujeme snadno podle
požadavku (od kořene k listům). Jinak vezmeme kružnici, odebereme její hrany a indukcí zbytek
zorientujeme. K tomu přidáme tuto kružnici zorientovanou do cyklu.
Z 15 bodů na tuto část bylo udělováno podle zásluh, tedy podle přiblížení se k nějakému správnému
důkazu.
4
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.
Vzorové výsledky (řešení):
Výsledem je 6 vzájemně neisomorfních grafů. Valná většina z vás správně odhalila, že záleží jedině
na tom, kolik "nesymetrických" vrcholů nakreslený graf obsahuje. Přesně řečeno, kolik je vrcholových
orbit grupy automorfismů.
Přitom ve variantách B,D bylo poměrně snadnější ty správné symetrie nalézt, ale jen málokdo
se vyrovnal i s požadavkem zdůvodnění, tedy vysvětlit i proč další symetrie nejsou. (To byl častý
důvod ztráty bodů i při správně určeném počtu.)
Ve variantách A,C bylo více symetrií k objevení, které jen někteří našli a ostatní pak většinou měli
odpovědi jako 5 nebo 6 získané z objevení té snadnější (zrcadlové) symetrie. Pokud však postup byl
správně systematický a jedinou chybou bylo neobjevení té dodatečné "skryté" symetrie, uděloval
jsem také dost hodně bodů. (Podívejte se na svůj příklad znovu. . . )
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).
5
a) Jak velká je nejdelší kružnice v tomto grafu?
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.
Vzorové výsledky (řešení):
a) Nejdelší kružnice v tomto grafu má všech 11 vrcholů. Zajímavé, že? Jen málokdo ji našel.
b) S nakreslením požadovaného grafu nebyl obvykle problém.
c) Barevnost grafu je 4, obarvení není obtížné. Potěšili jste mě, že většina i správně zdůvodnila,
proč graf nelze obarvit 3 barvami: Vnější C5 vyžaduje 3 barvy a až na symetrii je takové obarvení
jednoznačné (to je klíčové). Pak vrcholy kolem středového také dostanou 3 různé barvy, jak lze
zdůvodnit z obrázku, a prostřední vrchol už čtvrtou barvu vyžaduje.
Za každou část bylo po 5 bodů, přičemž hlavním důvodem ubírání bodů bylo nedostatečné zdůvodnění
tam, kde bylo potřeba. Jelikož se varianta B ukázala znatelně obtížnější, všichni její účastnící
obdrželi +1 bod navíc.
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 mimointervalového
grafu.
Vzorové výsledky (řešení):
Dá se říci, že nikdo část a) správně neudělal. Pokusy barvit vrcholy od nejvyšších stupňů a podobně
jsou předem odsouzeny k nezdaru, neboť problém barevnosti je NP-úplný. Aby byl váš postup barvení
použitelný, musí podstatným způsobem využívat strukturu dané intervalové reprezentace. Bohužel
však ani pozorování, že každý další vrchol x mimo největší kliku je s některým vrcholem v kliky
nespojený k ničemu nevede, neboť i když x obarvíme stejnou barvou jako v, takových x může být
více a některé z nich budou jako intervaly disjunktní, tudíž nemůžete všem přiřadit stejnou barvu!
Správným přístupem bylo nejprve udělat algoritmus pro část b). To se některým povedlo velmi
pěkně. Opět však bylo mnoho pokusů snažících se prohledávat kliky nebo barvit hladově podle
stupňů vrcholů, které byly předem odsouzeny k nezdaru (opět je důvodem NP-úplnost problémů
barevnosti i kliky).
Správný barvící algoritmus je následovný:
 Intervaly si seřadíme podle začátků zleva. Štětec si namočíme do barvy 1.
 Mějme štětec namočený barvou c. Postupujeme směrem doprava. Dokud objevujeme jen nové
začátky intervalů, barvíme je všechny barvou c.
 Jakmile narazíme na konec některého intervalu barvy c (intervalů barev < c si nevšímáme),
barvu si změníme na c + 1 a pokračujeme předchozím.
Snadnou analýzou tohoto algoritmu nejen ukážeme jeho korektnost, ale také vidíme, že posloupnost
vybraných intervalů, po kterých jsme měnili barvy, tvoří kliku, takže počet použitých barev je roven
velikosti největší kliky.
Studenti mířící neperspektivními směry jsem odměňoval drobnými pár body, vyšší bodování dostávali
nakonec jen ti, kteří se aspoň přiblížili k podání výše uvedeného algoritmu. Ovšem pozor,
byly mnohé marné pokusy o algoritmus, které na první pohled mohou vypadat podobně, ale jejich
společnou chybou bylo, že barvu 1 používali pro všechny další intervaly překrývající se s prvním. To
samozřejmě nelze, ty další intervaly mohou být mezi sebou disjunktní. Klíčovou myšlenkou postupu
je, že k další barvě musíme přejít, jakmile některý interval první skončí, a pokud u vás tato myšlenka
není obsažena, body za takový pokus nebudou.
6
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?
Vzorové výsledky (řešení):
Nejprve se podíváme na druhou otázku za 5 bodů, kterou skoro každý zvládl. Stačí se podívat na
graf K2 se stupni 1, do každého jeho vrcholu by muselo přicházet 0 hran, což nelze.
Hlavní otázka už dopadala hůře. Někteří se k ní snažili přistupovat přes kreslení grafu jedním
tahem a zorientování tohoto tahu, ale dělalo jim problém se vyrovnat s vrcholy lichých stupňů. Jiní
zkoušeli důkaz indukcí přes počet vrcholů, ale těm se vůbec nepovedl indukční krok, takže takové
pokusy byly neuznatelné. Dá se to i tak, ale pro indukční předpoklad se musí hrany přidávaného
vrcholu vhodně "přemostit".
Nejhezčí řešení vymyslelo pár studentů, kteří si všimli významné role zorientovaných kružnic.
(Bohužel nikdo z nich ani toto hezké řešení nedotáhl do formálně správného důkazu.) Formálně
postupujeme indukcí podle počtu kružnic či počtu hran grafu. Stromy zorientujeme snadno podle
požadavku (od kořene k listům). Jinak vezmeme kružnici, odebereme její hrany a indukcí zbytek
zorientujeme. K tomu přidáme tuto kružnici zorientovanou do cyklu.
Z 15 bodů na tuto část bylo udělováno podle zásluh, tedy podle přiblížení se k nějakému správnému
důkazu.
7
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.
Vzorové výsledky (řešení):
Výsledem je 3 vzájemně neisomorfních grafů. Valná většina z vás správně odhalila, že záleží jedině
na tom, kolik "nesymetrických" vrcholů nakreslený graf obsahuje. Přesně řečeno, kolik je vrcholových
orbit grupy automorfismů.
Přitom ve variantách B,D bylo poměrně snadnější ty správné symetrie nalézt, ale jen málokdo
se vyrovnal i s požadavkem zdůvodnění, tedy vysvětlit i proč další symetrie nejsou. (To byl častý
důvod ztráty bodů i při správně určeném počtu.)
Ve variantách A,C bylo více symetrií k objevení, které jen někteří našli a ostatní pak většinou měli
odpovědi jako 5 nebo 6 získané z objevení té snadnější (zrcadlové) symetrie. Pokud však postup byl
správně systematický a jedinou chybou bylo neobjevení té dodatečné "skryté" symetrie, uděloval
jsem také dost hodně bodů. (Podívejte se na svůj příklad znovu. . . )
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).
8
a) Jak velká je nejkratší kružnice v tomto grafu?
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.
Vzorové výsledky (řešení):
a) Nejkratší kružnice v tomto grafu je C4.
b) S nakreslením požadovaného grafu nebyl obvykle problém.
c) Barevnost grafu je 4, obarvení není obtížné. Potěšili jste mě, že většina i správně zdůvodnila,
proč graf nelze obarvit 3 barvami: Vnější C5 vyžaduje 3 barvy a až na symetrii je takové obarvení
jednoznačné (to je klíčové). Pak vrcholy kolem středového také dostanou 3 různé barvy, jak lze
zdůvodnit z obrázku, a prostřední vrchol už čtvrtou barvu vyžaduje.
Za každou část bylo po 5 bodů, přičemž hlavním důvodem ubírání bodů bylo nedostatečné zdůvodnění
tam, kde bylo potřeba. Jelikož se varianta B ukázala znatelně obtížnější, všichni její účastnící
obdrželi +1 bod navíc.
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 mimointervalového
grafu.
Vzorové výsledky (řešení):
Dá se říci, že nikdo část a) správně neudělal. Pokusy barvit vrcholy od nejvyšších stupňů a podobně
jsou předem odsouzeny k nezdaru, neboť problém barevnosti je NP-úplný. Aby byl váš postup barvení
použitelný, musí podstatným způsobem využívat strukturu dané intervalové reprezentace. Bohužel
však ani pozorování, že každý další vrchol x mimo největší kliku je s některým vrcholem v kliky
nespojený k ničemu nevede, neboť i když x obarvíme stejnou barvou jako v, takových x může být
více a některé z nich budou jako intervaly disjunktní, tudíž nemůžete všem přiřadit stejnou barvu!
Správným přístupem bylo nejprve udělat algoritmus pro část b). To se některým povedlo velmi
pěkně. Opět však bylo mnoho pokusů snažících se prohledávat kliky nebo barvit hladově podle
stupňů vrcholů, které byly předem odsouzeny k nezdaru (opět je důvodem NP-úplnost problémů
barevnosti i kliky).
Správný barvící algoritmus je následovný:
 Intervaly si seřadíme podle začátků zleva. Štětec si namočíme do barvy 1.
 Mějme štětec namočený barvou c. Postupujeme směrem doprava. Dokud objevujeme jen nové
začátky intervalů, barvíme je všechny barvou c.
 Jakmile narazíme na konec některého intervalu barvy c (intervalů barev < c si nevšímáme),
barvu si změníme na c + 1 a pokračujeme předchozím.
Snadnou analýzou tohoto algoritmu nejen ukážeme jeho korektnost, ale také vidíme, že posloupnost
vybraných intervalů, po kterých jsme měnili barvy, tvoří kliku, takže počet použitých barev je roven
velikosti největší kliky.
Studenti mířící neperspektivními směry jsem odměňoval drobnými pár body, vyšší bodování dostávali
nakonec jen ti, kteří se aspoň přiblížili k podání výše uvedeného algoritmu. Ovšem pozor,
byly mnohé marné pokusy o algoritmus, které na první pohled mohou vypadat podobně, ale jejich
společnou chybou bylo, že barvu 1 používali pro všechny další intervaly překrývající se s prvním. To
samozřejmě nelze, ty další intervaly mohou být mezi sebou disjunktní. Klíčovou myšlenkou postupu
je, že k další barvě musíme přejít, jakmile některý interval první skončí, a pokud u vás tato myšlenka
není obsažena, body za takový pokus nebudou.
9
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?
Vzorové výsledky (řešení):
Nejprve se podíváme na druhou otázku za 5 bodů, kterou skoro každý zvládl. Stačí se podívat na
graf K2 se stupni 1, do každého jeho vrcholu by muselo přicházet 0 hran, což nelze.
Hlavní otázka už dopadala hůře. Někteří se k ní snažili přistupovat přes kreslení grafu jedním
tahem a zorientování tohoto tahu, ale dělalo jim problém se vyrovnat s vrcholy lichých stupňů. Jiní
zkoušeli důkaz indukcí přes počet vrcholů, ale těm se vůbec nepovedl indukční krok, takže takové
pokusy byly neuznatelné. Dá se to i tak, ale pro indukční předpoklad se musí hrany přidávaného
vrcholu vhodně "přemostit".
Nejhezčí řešení vymyslelo pár studentů, kteří si všimli významné role zorientovaných kružnic.
(Bohužel nikdo z nich ani toto hezké řešení nedotáhl do formálně správného důkazu.) Formálně
postupujeme indukcí podle počtu kružnic či počtu hran grafu. Stromy zorientujeme snadno podle
požadavku (od kořene k listům). Jinak vezmeme kružnici, odebereme její hrany a indukcí zbytek
zorientujeme. K tomu přidáme tuto kružnici zorientovanou do cyklu.
Z 15 bodů na tuto část bylo udělováno podle zásluh, tedy podle přiblížení se k nějakému správnému
důkazu.
10
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.
Vzorové výsledky (řešení):
Výsledem je 5 vzájemně neisomorfních grafů. Valná většina z vás správně odhalila, že záleží jedině
na tom, kolik "nesymetrických" vrcholů nakreslený graf obsahuje. Přesně řečeno, kolik je vrcholových
orbit grupy automorfismů.
Přitom ve variantách B,D bylo poměrně snadnější ty správné symetrie nalézt, ale jen málokdo
se vyrovnal i s požadavkem zdůvodnění, tedy vysvětlit i proč další symetrie nejsou. (To byl častý
důvod ztráty bodů i při správně určeném počtu.)
Ve variantách A,C bylo více symetrií k objevení, které jen někteří našli a ostatní pak většinou měli
odpovědi jako 5 nebo 6 získané z objevení té snadnější (zrcadlové) symetrie. Pokud však postup byl
správně systematický a jedinou chybou bylo neobjevení té dodatečné "skryté" symetrie, uděloval
jsem také dost hodně bodů. (Podívejte se na svůj příklad znovu. . . )
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).
11
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?
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.
Vzorové výsledky (řešení):
a) Nejmenší podmnožina X jeho vrcholů taková, že každý jeho vrchol mimo X má nějakého
souseda v X, má 3 vrcholy.
b) S nakreslením požadovaného grafu nebyl obvykle problém.
c) Barevnost grafu je 4, obarvení není obtížné. Potěšili jste mě, že většina i správně zdůvodnila,
proč graf nelze obarvit 3 barvami: Vnější C5 vyžaduje 3 barvy a až na symetrii je takové obarvení
jednoznačné (to je klíčové). Pak vrcholy kolem středového také dostanou 3 různé barvy, jak lze
zdůvodnit z obrázku, a prostřední vrchol už čtvrtou barvu vyžaduje.
Za každou část bylo po 5 bodů, přičemž hlavním důvodem ubírání bodů bylo nedostatečné zdůvodnění
tam, kde bylo potřeba. Jelikož se varianta B ukázala znatelně obtížnější, všichni její účastnící
obdrželi +1 bod navíc.
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 mimointervalového
grafu.
Vzorové výsledky (řešení):
Dá se říci, že nikdo část a) správně neudělal. Pokusy barvit vrcholy od nejvyšších stupňů a podobně
jsou předem odsouzeny k nezdaru, neboť problém barevnosti je NP-úplný. Aby byl váš postup barvení
použitelný, musí podstatným způsobem využívat strukturu dané intervalové reprezentace. Bohužel
však ani pozorování, že každý další vrchol x mimo největší kliku je s některým vrcholem v kliky
nespojený k ničemu nevede, neboť i když x obarvíme stejnou barvou jako v, takových x může být
více a některé z nich budou jako intervaly disjunktní, tudíž nemůžete všem přiřadit stejnou barvu!
Správným přístupem bylo nejprve udělat algoritmus pro část b). To se některým povedlo velmi
pěkně. Opět však bylo mnoho pokusů snažících se prohledávat kliky nebo barvit hladově podle
stupňů vrcholů, které byly předem odsouzeny k nezdaru (opět je důvodem NP-úplnost problémů
barevnosti i kliky).
Správný barvící algoritmus je následovný:
 Intervaly si seřadíme podle začátků zleva. Štětec si namočíme do barvy 1.
 Mějme štětec namočený barvou c. Postupujeme směrem doprava. Dokud objevujeme jen nové
začátky intervalů, barvíme je všechny barvou c.
 Jakmile narazíme na konec některého intervalu barvy c (intervalů barev < c si nevšímáme),
barvu si změníme na c + 1 a pokračujeme předchozím.
Snadnou analýzou tohoto algoritmu nejen ukážeme jeho korektnost, ale také vidíme, že posloupnost
vybraných intervalů, po kterých jsme měnili barvy, tvoří kliku, takže počet použitých barev je roven
velikosti největší kliky.
Studenti mířící neperspektivními směry jsem odměňoval drobnými pár body, vyšší bodování dostávali
nakonec jen ti, kteří se aspoň přiblížili k podání výše uvedeného algoritmu. Ovšem pozor,
byly mnohé marné pokusy o algoritmus, které na první pohled mohou vypadat podobně, ale jejich
společnou chybou bylo, že barvu 1 používali pro všechny další intervaly překrývající se s prvním. To
samozřejmě nelze, ty další intervaly mohou být mezi sebou disjunktní. Klíčovou myšlenkou postupu
12
je, že k další barvě musíme přejít, jakmile některý interval první skončí, a pokud u vás tato myšlenka
není obsažena, body za takový pokus nebudou.
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?
Vzorové výsledky (řešení):
Nejprve se podíváme na druhou otázku za 5 bodů, kterou skoro každý zvládl. Stačí se podívat na
graf K2 se stupni 1, do každého jeho vrcholu by muselo přicházet 0 hran, což nelze.
Hlavní otázka už dopadala hůře. Někteří se k ní snažili přistupovat přes kreslení grafu jedním
tahem a zorientování tohoto tahu, ale dělalo jim problém se vyrovnat s vrcholy lichých stupňů. Jiní
zkoušeli důkaz indukcí přes počet vrcholů, ale těm se vůbec nepovedl indukční krok, takže takové
pokusy byly neuznatelné. Dá se to i tak, ale pro indukční předpoklad se musí hrany přidávaného
vrcholu vhodně "přemostit".
Nejhezčí řešení vymyslelo pár studentů, kteří si všimli významné role zorientovaných kružnic.
(Bohužel nikdo z nich ani toto hezké řešení nedotáhl do formálně správného důkazu.) Formálně
postupujeme indukcí podle počtu kružnic či počtu hran grafu. Stromy zorientujeme snadno podle
požadavku (od kořene k listům). Jinak vezmeme kružnici, odebereme její hrany a indukcí zbytek
zorientujeme. K tomu přidáme tuto kružnici zorientovanou do cyklu.
Z 15 bodů na tuto část bylo udělováno podle zásluh, tedy podle přiblížení se k nějakému správnému
důkazu.