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

7 GG•
9
''
s
9
))
7 GG
5
ff
•
2
yy
3 GG 8
3

3
yy
8 GG
3
ÑÑ
• 2 GG
3

2
yy
t
•
5
ee
4
GG•
3
ee
3
GG•
6
ee
3. (5 bodů) Dejte příklad souvislého grafu s osmi vrcholy, který je izomorfní svému
blokovému stromu. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad eulerovského grafu G s osmi vrcholy splňujícího κ (G) = 3.
Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad 5-regulárního grafu G s osmi vrcholy splňujícího κ(G) = 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) = 3 a neobsahují podgraf izomorfní K3.
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 = (V, E) je obyčejný graf, kde
V = vi,k i ∈ {1, 2}, k ∈ {1, . . . , n}
a pro všechna i, j ∈ {1, 2} a k, ∈ {1, . . . , n} platí vi,kvj, ∈ E právě tehdy, když
(i, k) = (j, ) ∧ |k − | ≤ 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 střed grafu.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pokud obyčejný graf G neobsahuje vrchol stupně alespoň 4,
tak platí rovnost κ(G) = κ (G).