Teorie grafů – podzim 2018 – 2. termín
1. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami
hran a dvou vrcholů a svoje rozhodnutí zdůvodněte.
• 7 GG 6
3

7 GG•
9
''
s
9
))
7 GG
5
ff
•
2
yy
3 GG 8
3

3
yy
8 GG
3
ÑÑ
• 2 GG
3

2
yy
t
•
5
ee
4
GG•
3
ee
3
GG•
6
ee
2. (10 bodů) Určete počet uzavřených sledů délky 8 v grafu
A B
C D
3. (5 bodů) Dejte příklad 3-regulárního grafu G, který má osm vrcholů a splňuje
κ (G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad ohodnoceného grafu s šesti vrcholy takového, že Dijkstrův
algoritmus nedává správný výsledek při výpočtu nejkratších cest z žádného jeho
vrcholu. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad obyčejného grafu s osmi vrcholy, který má právě dvě
kostry. 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é
nejsou hamiltonovské a splňují κ(G) = 2.
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 je kladné celé číslo a nechť G je obyčejný graf s 2n vrcholy
ui a vi, pro i = 1, . . . , n, a s hranami uiuj a uivj, pro i, j = 1, . . . , n, i = 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 Eulerův vztah.
13. (10 bodů) Dokažte, že v libovolném 2-souvislém grafu mají každé dvě nejdelší
kružnice alespoň jeden společný vrchol.