Teorie grafů – podzim 2023 – 5. 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 obyčejného grafu G, který má pět vrcholů a splňuje podmínky
κ(G) = χ (G) = 0. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad obyčejného grafu G s osmi vrcholy, který splňuje κ(G) = 1
a κ (G) = 2 a minimum ze stupňů jeho vrcholů je 3. Pokud takový graf neexistuje,
zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého obyčejného grafu G se šesti vrcholy a jeho dvou
vrcholů u a v takových, že v G existuje právě jedna cesta délky čtyři z u do v a
právě tři tahy délky čtyři z u do v. 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, x + 2, 5, y)
skórem nějakého obyčejného grafu, a svoje rozhodnutí zdůvodněte. Pro všechny
takové hodnoty x a y dejte příklad obyčejného grafu s tímto skóre.
7. (10 bodů) Najděte všechny vzájemně neizomorfní 2-souvislé grafy se sedmi vrcholy,
které přestanou být 2-souvislé po odebrání libovolné hrany.
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 vrcholy
u1, . . . , un+1, v1, . . . , vn, w1, . . . , wn+1
a hranami
uiuj, wiwj pro i, j ∈ {1, . . . , n + 1}, i = j,
uivj, wivj pro i ∈ {1, . . . , n + 1}, j ∈ {1, . . . , n}.
Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické
číslo a zda je G eulerovský nebo 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ů) Pro každé přirozené číslo n dokažte, že pokud v každém podgrafu
grafu G = (V, E) existuje vrchol stupně menšího než 2n
, tak existují podmnožiny
E1, . . . , En ⊆ E takové, že E = E1 ∪ · · · ∪ En a grafy (V, E1), . . . , (V, En) jsou
bipartitní.