Teorie grafů – podzim 2023 – 3. termín
1. (10 bodů) Následující tabulka vyjadřuje odhad pravděpodobnosti, která strana se
dostane k moci v následujících volbách, v závislosti na tom, kdo vládl v posledních
dvou volebních obdobích. Určete, s jakou pravděpodobností bude po proběhnutí
čtyř voleb u moci levice, jestliže právě vládne pravice a v minulém volebním období
vládla levice.
předchozí vláda současná vláda zvítězí levice zvítězí pravice
levice levice 1/6 5/6
levice pravice 2/3 1/3
pravice pravice 5/6 1/6
pravice levice 1/2 1/2
2. (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
3. (5 bodů) Dejte příklad 2-souvislého obyčejného grafu s osmi vrcholy a 13 hranami
takového, že po odstranění libovolné hrany zůstane hranově 2-souvislý, ale po
odstranění některé hrany přestane být 2-souvislý. Pokud takový graf neexistuje,
zdůvodněte proč.
4. (5 bodů) Dejte příklad eulerovského rovinného obyčejného grafu se 14 vrcholy,
který nemá čtyři vrcholy stejného stupně. Pokud takový graf neexistuje, zdůvodněte
proč.
5. (5 bodů) Dejte příklad 3-souvislého obyčejného grafu G = (V, E) s osmi vrcholy,
který má jediný izomorfismus na sebe různý od identity a tento izomorfismus
ϕ splňuje ϕ(v) = v pro všechny vrcholy v ∈ 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, x, 4, y, y, y + 1)
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 se šesti vrcholy,
které splňují rovnosti κ(G) = 1 a χ(G) = χ (G) = 3.
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, uivi+1, vivi+1, wivi+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 blokový strom souvislého grafu, včetně v definici použitých
pojmů.
12. (5 bodů) Formulujte vzorec pro výpočet největší velikosti párování a podmínku
charakterizující existenci perfektního párování v obyčejném grafu.
13. (10 bodů) Dokažte, že každý 2-souvislý graf má alespoň tolik koster jako hran.