Teorie grafů – podzim 2018 – 3. termín
1. (10 bodů) Na následujícím grafu předveďte běh Dijkstrova algoritmu s počátečním
vrcholem E. Vyznačte algoritmem získaný strom nejkratších cest.
A 1
0
B
2
3
2
0
C
2
D 1
3
2
E
4
1
F
3
1
G
1
H
0
I
2. (10 bodů) Určete chromatický polynom grafu K2,3.
3. (5 bodů) Dejte příklad souvislého grafu G se sedmi vrcholy, který není eulerovský
a splňuje nerovnost κ (G) ≥ χ (G). Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu se šesti vrcholy, který splňuje χ(G) = 4 a přitom
neobsahuje podgraf izomorfní grafu K4. 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
obsahuje právě čtyři vrcholy. 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 + 4)
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 vrcholovou a hranovou souvislost grafu κ a κ .
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pro všechna přirozená čísla k a n splňující k ≤ n − 2
je největší vzdálenost vrcholů v nějakém k-souvislém grafu o n vrcholech rovna
n−2
k
+ 1.