Teorie grafů – podzim 2022 – 5. 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ů) 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
3. (5 bodů) Dejte příklad obyčejného grafu se šesti vrcholy a jeho dvou vrcholů u
a v takových, že počet sledů délky 4 z u do v je vyšší než počet tahů délky 4 z u
do v, a ten je vyšší než počet cest délky 4 z u do v. Pokud takový graf neexistuje,
zdůvodněte proč.
4. (5 bodů) Dejte příklad obyčejného grafu G s deseti vrcholy, který neobsahuje
vrchol stupně 3 a splňuje κ(G) = 2 a κ (G) = 3. Pokud takový graf neexistuje,
zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého bipartitního grafu s 11 vrcholy a 11 hranami,
který má následující blokový strom. 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 G se sedmi
vrcholy, které neobsahují podgraf izomorfní grafu K3 a splňují χ(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 je následující graf 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 celé číslo a G je obyčejný graf sestávající ze dvou kružnic
s vrcholy v1, . . . , vn a w1, . . . , wn (vrcholy leží na kružnicích v uvedeném pořadí)
a dvou vrcholů v a w, přičemž G dále obsahuje právě hrany vw, vvi, wwi, viwi,
pro i = 1, . . . , n. Určete hranovou a vrcholovou souvislost grafu G, jeho hranové
a vrcholové chromatické číslo a zda je G eulerovský nebo hamiltonovský.
11. (5 bodů) Definujte rezervní polocestu a její rezervu.
12. (5 bodů) Formulujte větu o největších párováních a vrcholových pokrytích v bipartitních
grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Dokažte, že pro každý 3-regulární graf G splňující κ(G) = 1 platí
χ (G) = 4.