Teorie grafů – podzim 2021 – 2. termín
1. (10 bodů) Dva lékařské týmy, jejichž členové jsou označeni písmeny α až ι, respektive
a až i, spolu soutěží, kdo naočkuje současně více nedůvěřivých důchodců.
Následující tabulky udávají pro každého důchodce (označeni písmeny A až I a
čísly 1 až 9), kterými lékaři je ochoten se nechat naočkovat.
A δ, ε B δ, ε, ι C α, β, ζ, η, ϑ D β, ι E δ, ι F γ, ζ, ϑ, ι
G β, δ, ι H δ, ε I α, γ, η, ϑ, ι
1 a, b, c 2 a, d, f 3 a, b, c, h, i 4 b, c, d, e, h, i 5 a, d, f
6 d, f, g 7 a, d, g 8 d, f, g 9 e, g, h, i
Oba týmy přidělí důchodce lékařům optimálním způsobem. Rozhodněte, který
z týmů zvítězí. Svoje rozhodnutí zdůvodněte.
2. (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
5 GG
3
bb
•
2
yy
0
00
5 GG• 2 GG
0
ÐÐ
3

t
• 3
GG
2
yy
• 4
GG• 5
GG•
3
cc
• 0
GG
2
yy
• 0
GG• 0
GG•
3
cc
3. (5 bodů) Dejte příklad souvislého grafu se sedmi vrcholy, který má právě 11
koster. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 2-souvislého grafu se sedmi vrcholy, který má jediný izomorfismus
na sebe. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého grafu G se sedmi vrcholy, který není eulerovský,
splňuje nerovnost χ(G) ≥ χ (G) a neobsahuje vrchol stupně χ(G). Pokud takový
graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(1, 1, 1, 1, 2, x, 4, y, x + 3)
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 šesti vrcholy,
které nejsou hamiltonovské.
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 blokový strom souvislého grafu.
12. (5 bodů) Formulujte větu o největších párováních a vrcholových pokrytích v bipartitních
grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Pomocí Tutteho věty dokažte, že každý 3-regulární 2-souvislý graf má
perfektní párování.