Teorie grafů – podzim 2019 – 3. termín
1. (10 bodů) Použitím některého algoritmu založeného na standardních operacích
s maticemi určete vzdálenosti mezi všemi dvojicemi vrcholů následujícího grafu.
Přitom vrcholy v matici reprezentujte v pořadí v1, v2, v3, v4, v5.
v1
4
~~
2

6
22
v2
1
bb
4
GG
2
22
v3
1

5
yy
1
GG v4
2
––
2oo
5
~~
v5
2
––
6
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

10
))
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
5 GG
3
bb
•
2
yy
0
00
5 GG• 2 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 grafu se šesti vrcholy, který není bipartitní a
v němž největší párování obsahuje právě dvě hrany. Pokud takový graf neexistuje,
zdůvodněte proč.
4. (5 bodů) Dejte příklad souvislého bipartitního grafu G s osmi vrcholy, který obsahuje
tři hrany, které neleží na stejné kostře grafu G. Pokud takový graf neexistuje,
zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G s deseti vrcholy, který neobsahuje vrchol stupně
3 a splňuje κ(G) = 2 a κ (G) = 3. 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, y, y, y + 1)
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í souvislé grafy G s osmi vrcholy,
které neobsahují cestu délky 5 a jejichž blokový strom má právě 6 vrcholů.
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 sestávající z kružnice
délky n a dvou dalších vrcholů, které jsou spojeny hranami právě s vrcholy této
kružnice. 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 Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pro libovolný graf G = (V, E) platí 2κ (G) ≤ κ(G)+|V |−1.