Teorie grafů – podzim 2021 – 5. termín
1. (10 bodů) Následující graf vyjadřuje pravděpodobnost, do které z místností A,
B, C, D se nehlídané dítě přesune během jedné minuty. Určete, do které místnosti
je třeba dítě umístit, chceme-li maximalizovat pravděpodobnost, že když se je po
čtyřech minutách vydáme hledat, najdeme je hned v první prohledávané místnosti.
(Jako první prohledáváme samozřejmě místnost, kde se dítě nachází s největší
pravděpodobností.)
A
1
2

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

C
1
2
yy
1
2
GG D
1
4
oo
1
4
••
1
2
yy
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 2-souvislého 3-regulárního grafu se čtrnácti vrcholy, který
není hamiltonovský. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad hranově 3-souvislého grafu s deseti vrcholy a jeho dvou
vrcholů u a v takových, že počet tahů z u do v je přesně o pět vyšší než počet cest
z u do v. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad eulerovského grafu G se šesti vrcholy, který splňuje rovnost
χ(G) = 4. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která nezáporná celá čísla x a y je posloupnost
(x, x, x, x + 2, y, y + 2, y + 2, y + 2, y + 2)
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í obyčejné grafy se sedmi vrcholy
a šesti hranami, které mají právě jeden bod artikulace a obsahují kružnici.
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 celé číslo a nechť G je obyčejný graf, který vznikne
z grafu Kn,n provedením dělení jedné jeho hrany. Určete hranovou a vrcholovou
souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či
hamiltonovský.
11. (5 bodů) Definujte izomorfismus grafů.
12. (5 bodů) Formulujte větu o struktuře 2-souvislých grafů a vysvětlete všechny
pojmy, které se v ní vyskytují.
13. (10 bodů) Dokažte, že každý 2-souvislý graf o n vrcholech, který není izomorfní
grafu Cn, má alespoň 3n − 4 koster.