Teorie grafů – podzim 2021 – 4. termín
1. (10 bodů) Následující graf vyjadřuje pravděpodobnost přechodu systému mezi
stavy A, B, C a D během jednoho kroku. Určete, ve kterém stavu je třeba práci
systému zahájit, aby pravděpodobnost, že po čtyřech krocích bude ve stavu D,
byla co největší.
A
1
2

1
4
//
1
4

B
3
4
oo
1
4

C
1
2
OO
1
2
// D
1
4oo
1
4
__
1
2
QQ
2. (10 bodů) Na následujícím grafu předveďte běh Dijkstrova algoritmu s počátečním
vrcholem s. Vyznačte algoritmem získaný strom nejkratších cest.
•
1
1
3
•
2
4
•
1 0
•
1
•
3
s
6
1
•
4
2
•
1
• 1
•
3. (5 bodů) Dejte příklad 2-souvislého grafu se sedmi vrcholy, který není eulerovský
ani hamiltonovský, ale přidáním jedné hrany lze dosáhnout toho, aby eulerovský i
hamiltonovský byl. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad obyčejného grafu G se sedmi vrcholy a jeho dvou vrcholů
u a v takových, že počet tahů z u do v je o 1 vyšší než počet cest z u do v. Pokud
takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který splňuje κ(G) = 2 a
přidáním libovolné hrany se hodnota κ(G) zvýší. 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, 1, 1, x, 4, y, 2x + 1)
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í souvislé grafy se sedmi vrcholy,
které mají právě 12 koster.
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 ≥ 1 je přirozené číslo a G je obyčejný graf tvořený n disjunktními
cykly délky 3 a dvěma dalšími vrcholy, přičemž oba tyto vrcholy jsou
spojeny hranami právě se všemi třemi vrcholy všech n cyklů. 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 Tutteho větu o perfektním párování 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.