Teorie grafů – podzim 2023 – 4. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
2
•
3
2 4
2
•
2
5 •
3
2
• 5
• 4
•
2. (10 bodů) Následující graf vyjadřuje pravděpodobnost, do které z místností kuchyň,
jídelna, obývák a ložnice se nehlídané dítě přesune během čtvrt minuty.
Určete, ve které místnosti je třeba dítě opustit, chceme-li maximalizovat pravděpodobnost,
že když se je po minutě vydáme hledat, najdeme je nejpozději ve druhé
prohledávané místnosti. (Jako první prohledáváme samozřejmě místnosti, kde se
dítě nachází s největší pravděpodobností.)
K
1
2

1
4
//
1
4

J
3
4
oo
1
4

O
1
2
OO
1
2
// L
1
4
oo
1
4
__
1
2
OO
3. (5 bodů) Dejte příklad 4-souvislého obyčejného grafu s osmi vrcholy, který nemá
perfektní párování. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad obyčejného grafu G se 14 vrcholy, který splňuje rovnosti
κ(G) = 1 a κ (G) = 2 a jehož blokový strom má jediný izomorfismus na sebe.
Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad 2-souvislého obyčejného grafu se šesti vrcholy a jeho dvou
vrcholů u a v takových, že existuje právě deset cest z u do v. 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, 2, 2, 3, 4, 5, x, y)
skórem nějakého obyčejného grafu, a svoje rozhodnutí zdůvodněte. Pro všechny
takové hodnoty x a y dejte příklad obyčejného grafu s tímto skóre.
7. (10 bodů) Najděte všechny vzájemně neizomorfní obyčejné grafy G = (V, E)
s osmi vrcholy takové, že pro každou dvojici vrcholů u, v ∈ V existuje izomorfismus
ϕ grafu G na sebe splňující ϕ(u) = v.
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 ≥ 3 je přirozené číslo a G je obyčejný graf s 3n vrcholy ui, vi,
wi, pro i = 1, . . . , n, a hranami uivi, viwi, uiui+1, uiwi+1, vivi+1, wiui+1 a wiwi+1,
pro i = 1, . . . , n, kde un+1 = u1, vn+1 = v1 a wn+1 = w1. Určete hranovou a
vrcholovou souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G
eulerovský nebo hamiltonovský.
11. (5 bodů) Definujte κ a κ a vysvětlete v definicích použité pojmy.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že obsahuje-li 3-souvislý graf kružnici liché délky, potom
obsahuje takové kružnice aspoň čtyři.