Teorie grafů – podzim 2014 – 4. termín
1. (10 bodů) Určete počet sledů délky osm z vrcholu A do vrcholu B v grafu
A B
⑦⑦⑦⑦⑦⑦⑦⑦
C
⑦⑦⑦⑦⑦⑦⑦⑦
D E
2. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami
hran a dvou vrcholů a svoje rozhodnutí zdůvodněte.
• 6 GG/.-,()*+5
3

4 GG•
4
''✽✽✽✽✽✽✽✽✽
3
'&%$!"#s
9
))❀❀❀❀❀❀❀❀
7 GG
4
ff✝✝✝✝✝✝✝✝✝
•
2
yy
2 GG/.-,()*+5
3
yy
3 GG
3
ÑÑ✄✄✄✄✄✄✄✄
3
ff✝✝✝✝✝✝✝✝✝
• 7 GG
3

'&%$!"#t
•
1
ee✄✄✄✄✄✄✄✄
7
GG•
3
yy
3
ee✄✄✄✄✄✄✄✄✄✄
3
GG•
7
ee✄✄✄✄✄✄✄✄
3. (5 bodů) Dejte příklad eulerovského 3-souvislého grafu se sedmi vrcholy, který
není hamiltonovský. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G s pěti vrcholy, který splňuje χ(G) = κ(G) a není
bipartitní. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad 2-souvislého grafu G s pěti vrcholy, který splňuje χ′
(G) =
4, ale odebráním kterékoli hrany se hodnota χ′
(G) sníží. Pokud takový graf neexistuje,
zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x, y a z je posloupnost
(1, 2, 3, 4, 5, 6, x, y, z)
skórem nějakého grafu, a svoje rozhodnutí zdůvodněte. Pro všechny takové hodnoty
x, y a z dejte příklad grafu s tímto skóre.
7. (10 bodů) Najděte všechny vzájemně neizomorfní grafy G s osmi vrcholy, které
splňují κ′
(G) = κ(G) + 2.
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí
zdůvodněte.
•
✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭✭
✾✾✾✾✾✾✾✾ •
✆✆✆✆✆✆✆✆
✖✖✖✖✖✖✖✖✖✖✖✖✖✖✖✖✖✖✖ •
✴✴✴✴✴✴✴✴✴✴✴✴✴✴
❄❄❄❄❄❄❄❄❄ •
✂✂✂✂✂✂✂✂✂
✑✑✑✑✑✑✑✑✑✑✑✑✑✑
•
✾✾✾✾✾✾✾✾ •
✒✒✒✒✒✒✒✒✒✒✒✒✒ •
✎✎✎✎✎✎✎✎✎✎✎✎✎✎
❄❄❄❄❄❄❄❄❄ •
✲✲✲✲✲✲✲✲✲✲✲✲✲✲
• • •
⑧⑧⑧⑧⑧⑧⑧⑧⑧ •
❁❁❁❁❁❁❁❁❁
• • • •
9. (7 bodů) Rozhodněte, zda následující graf je rovinný. Pokud rovinný je, doplňte
jej na maximální rovinný graf. Pokud rovinný není, svoje rozhodnutí zdůvodněte.
•
✴✴✴✴✴✴✴✴✴✴✴ •
⑧⑧⑧⑧⑧⑧⑧
✎✎✎✎✎✎✎✎✎✎✎
❄❄❄❄❄❄❄
✴✴✴✴✴✴✴✴✴✴✴ •
•
❄❄❄❄❄❄❄
❖❖❖❖❖❖❖❖❖❖❖ • •
⑧⑧⑧⑧⑧⑧⑧
• • •
10. (10 bodů) Nechť n je přirozené číslo a G je obyčejný graf tvořený n kopiemi grafu
K4, přičemž i-tá kopie má vrcholy si, ti, ui a vi, a tyto kopie jsou spojeny hranami
sisi+1, titi+1, uiui+1 a vivi+1 pro i = 1, . . . , n − 1. Určete hranovou a vrcholovou
souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či
hamiltonovský.
11. (5 bodů) Definujte blok grafu.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že v rovinném grafu G = (V, E), který splňuje |E| > 5
2
|V |,
existuje komponenta s alespoň 13 vrcholy.