Teorie grafů – podzim 2022 – 1. termín
1. (10 bodů) Určete počet sledů v následujícím orientovaném grafu, které mají
délku 8 a končí ve vrcholu C.
A GG
22
Boo

C
yy bb
GG D
oo
2. (10 bodů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok
největší velikosti.
síť: •
3
ÐÐ
5 GG•
3

1
))
tok: •
2
ÐÐ
2 GG•
1

1
))
s
6
44
1
GG
4
UU
•
2

3 GG• 3 GG
3
’’
3
ÐÐ
4

t s
2
55
1
GG
3
UU
•
1

2 GG• 2 GG
1
’’
0
ÐÐ
0

t
• 6
GG•
3
••
3
GG•
7
cc
• 3
GG•
0
••
3
GG•
3
cc
3. (5 bodů) Dejte příklad 2-souvislého grafu, který má právě 12 koster. Pokud takový
graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad eulerovského grafu G se šesti vrcholy takového, že se
hodnota χ (G) liší od nejmenšího stupně vrcholu v G přesně o 1. Pokud takový
graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad obyčejného grafu s devíti vrcholy a jeho dvou vrcholů,
mezi nimiž vede právě pět tahů délky 4. Pokud takový graf neexistuje, zdůvodněte
proč.
6. (10 bodů) Určete, pro která nezáporná celá čísla x a y je posloupnost
(x, x, x, x + 2, y, y + 1, y + 2, y + 2, y + 2)
skórem nějakého grafu, a svoje rozhodnutí zdůvodněte. Pro všechny takové hodnoty
x a y dejte příklad grafu s tímto skóre.
7. (10 bodů) Najděte všechny vzájemně neizomorfní 2-souvislé grafy G se sedmi
vrcholy, které splňují χ(G) = κ (G) = κ(G) + 1.
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 ≥ 1 je přirozené číslo a G je obyčejný graf s 3n + 3 vrcholy
u, v, w a uk, vk, wk pro k = 1, . . . , n a s hranami uuk, vvk, wwk, ukvk, vkwk a
ukwk pro k = 1, . . . , n. Určete hranovou a vrcholovou souvislost G, jeho hranové
a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte blokový strom včetně v definici použitých pojmů.
12. (5 bodů) Formulujte Mengerovu větu o vrcholové souvislosti obyčejných grafů a
vysvětlete v ní použité pojmy.
13. (10 bodů) Buď G souvislý graf, který má právě dva bloky. Dokažte, že celý střed
grafu G je obsažen v jednom z těchto bloků.