Teorie grafů – podzim 2019 – 2. 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ých stavech je možné
práci systému zahájit, aby po dvou i po čtyřech krocích byla pravděpodobnost, že
systém bude ve stavu A, vyšší než pravděpodobnost, že bude ve stavu C.
A
1
2

1
4
GG
1
4
11
B
3
4
oo
1
4

C
1
2
yy
1
2
GG D
1
4oo
1
2
••
1
4

2. (10 bodů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok
největší velikosti.
síť: •
3
ÐÐ
5 GG•
3

1
))
tok: •
1
ÐÐ
3 GG•
2

1
))
s
6
44
1
GG
4
UU
•
2

3 GG• 3 GG
3
’’
3
ÐÐ
4

t s
2
55
1
GG
3
UU
•
1

1 GG• 2 GG
1
’’
0
ÐÐ
0

t
• 6
GG•
3
••
3
GG•
7
cc
• 3
GG•
0
••
3
GG•
3
cc
3. (5 bodů) Dejte příklad 5-souvislého rovinného grafu s deseti vrcholy. Pokud takový
graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 3-souvislého grafu se sedmi vrcholy, který není hamiltonovský.
Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého grafu se šesti vrcholy, který má právě 11 koster.
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, 4, 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é
splňují κ (G) = χ (G).
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 s 3n vrcholy
u1, v1, w1, . . . , un, vn, wn a s hranami uiuj a wiwj pro všechna i a j splňující i = j
a uivj a wivj pro všechna i a j. Určete hranovou a vrcholovou souvislost G, jeho
hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte blokový strom souvislého grafu, včetně v definici použitých
pojmů.
12. (5 bodů) Formulujte větu o největších párováních a o vrcholových pokrytích
v bipartitních grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Dokažte, že na libovolném ohodnoceném orientovaném grafu s více
než jedním vrcholem, který neobsahuje orientované kružnice se záporným součtem
ohodnocení hran, dá Dijkstrův algoritmus při hledání cest z libovolného daného
vrcholu správný výsledek alespoň pro dva vrcholy.