Teorie grafů – podzim 2020 – 1. 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 pravice, jestliže již druhé volební období vládne 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ů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok
největší velikosti.
síť: • 8 GG•
3
ÒÒ
9 GG•
3
((
8 GG•
3

9
))
tok: • 5 GG•
0
ÒÒ
5 GG•
0
((
5 GG•
0

5
))
s
5
33
5 GG
4
bb
•
3
yy
3
00
7 GG• 3 GG
3
ÐÐ
5

t s
2
44
3 GG
3
bb
•
2
yy
0
00
3 GG• 0 GG
0
ÐÐ
3

t
• 3
GG
2
yy
• 4
GG• 5
GG•
3
cc
• 0
GG
2
yy
• 0
GG• 0
GG•
3
cc
3. (5 bodů) Dejte příklad obyčejného grafu G se sedmi vrcholy, pro který platí
κ(G) = 3 a κ (G) = 4. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad neorientovaného grafu ohodnoceného reálnými čísly a jeho
dvou vrcholů u a v takových, že Dijkstrův algoritmus dá při výpočtu vzdáleností
d(u, v) a d(v, u) jistě různé výsledky a oba budou chybné. Pokud takový graf
neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad hranově 2-souvislého grafu s devíti vrcholy, který má právě
15 koster a dva body artikulace. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(2, 3, 4, 4, x, 6, 7, y, y)
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í grafy G se šesti vrcholy, které
jsou 2-souvislé, ale po odebrání libovolné hrany 2-souvislé nebudou.
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 tvořený n − 2
disjunktními cykly délky n, přičemž i-tý cyklus má vrcholy vi,1, . . . , vi,n (vrcholy
leží na cyklech v uvedeném pořadí). Tyto cykly jsou spojeny hranami vi,jvi+1,j pro
i ∈ {1, . . . , n − 3} a j ∈ {1, . . . , n}. Určete hranovou a vrcholovou souvislost G,
jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte, co znamená, že graf G je izomorfní indukovanému podgrafu
grafu H.
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 každé dvě nejdelší cesty v 2-souvislém grafu mají alespoň
dva společné vrcholy.