Teorie grafů – podzim 2022 – 4. termín
1. (10 bodů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok
největší velikosti.
síť: • 8 GG•
3
ÒÒ
9 GG•
3
((
8 GG•
3

10
))
tok: • 5 GG•
0
ÒÒ
5 GG•
0
((
5 GG•
0

5
))
s
5
33
5 GG
4
bb
•
3
yy
3
00
7 GG• 3 GG
3
ÐÐ
5

t s
2
44
4 GG
3
bb
•
2
yy
1
00
3 GG• 1 GG
0
ÐÐ
2

t
• 3
GG
2
yy
• 4
GG• 5
GG•
3
cc
• 0
GG
2
yy
• 1
GG• 1
GG•
3
cc
2. (10 bodů) Určete chromatický polynom grafu K2,3.
3. (5 bodů) Dejte příklad bipartitního grafu G s osmi vrcholy, který splňuje rovnosti
κ(G) = 2 a κ (G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 3-souvislého grafu G se šesti vrcholy, který splňuje rovnosti
χ(G) = 3 a χ (G) = 5. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu, který má následující blokový strom a jehož střed
sestává z jediného vrcholu. Pokud takový graf neexistuje, zdůvodněte proč.
• • •
• •
• • •
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(2, 3, 4, 4, 5, x, 7, y, y)
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 se sedmi vrcholy,
které přestanou být 2-souvislé po odebrání libovolné hrany.
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 ≥ 5 je celé číslo a nechť G je obyčejný graf s n vrcholy
ui a hranami uiui+1 a uiui+3, pro i ∈ {1, . . . , n}, kde un+k značí vrchol uk, pro
k ∈ {1, 2, 3}. Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové
chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte obyčejný graf a izomorfismus obyčejných grafů.
12. (5 bodů) Formulujte Tutteho větu o perfektním párování a vysvětlete v ní použité
pojmy.
13. (10 bodů) Dokažte, že v libovolném 2-souvislém grafu mají každé dvě nejdelší
kružnice alespoň jeden společný vrchol.