Teorie grafů – podzim 2023 – 1. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 4
2
•
4
2 2
5
•
1
5 •
3
2
• 2
• 4
•
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

9
))
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
3 GG
3
bb
•
2
yy
0
00
3 GG• 0 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 G s deseti vrcholy takového, že střed jeho
blokového stromu obsahuje více než jeden vrchol. Pokud takový graf neexistuje,
zdůvodněte proč.
4. (5 bodů) Dejte příklad 3-regulárního grafu se šestnácti vrcholy, který nemá žádné
perfektní párování. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G s osmi vrcholy, který má právě dva izomorfismy
na sebe a splňuje rovnosti κ(G) = 2 a κ (G) = 3. 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, x, 4, y, y, y + 1)
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í souvislé grafy G se sedmi hranami
a nejvýše šesti vrcholy splňující χ (G) = 4.
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 ≥ 0 je celé číslo a G je obyčejný graf s (n+3)·(2n+2) vrcholy
vi,j (pro i = 0, . . . , n+2 a j = 0, . . . , 2n+1) a hranami vi,jvi+1,j (pro i = 0, . . . , n+1
a j = 0, . . . , 2n+1), vi,jvi,j+1 (pro i = 0, . . . , n+2 a j = 0, . . . , 2n) a vn+2,jv0,2n+1−j
(pro j = 0, . . . , 2n + 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 následující pojmy: obyčejný graf, podgraf, izomorfismus grafů.
12. (5 bodů) Formulujte větu o největších párováních a o vrcholových pokrytích
v bipartitních grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Pro každé přirozené číslo n ≥ 2 dokažte, že neklesající posloupnost
(d1, . . . , dn) je skórem nějakého stromu právě tehdy, když platí
d1 ≥ 1 a d1 + · · · + dn = 2n − 2.