Teorie grafů – podzim 2017 – 1. termín
1. (10 bodů) Určete počet sledů v následujícím orientovaném grafu, které začínají
ve vrcholu C a mají délku osm.
A GG
22
Boo

C
yy bb
GG D
oo
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 souvislého grafu, který má právě sedm vrcholů, není stromem
a každý jeho vrchol stupně aspoň dva je bodem artikulace. Pokud takový
graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který je eulerovský a splňuje
κ(G) = χ(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad 3-souvislého nehamiltonovského grafu se sedmi vrcholy.
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, 2, x, y, 4, 4, x + y, x + 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í souvislé grafy G se šesti vrcholy
takové, že κ(G) je menší než stupeň každého vrcholu.
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 G je obyčejný graf s vrcholy ui, vi, wi a xi
pro i = 1, . . . , n a hranami uivi, uiwi, viwi, uixi, vixi, wixi, xiui+1, xivi+1 a xiwi+1
pro i = 1, . . . , n, kde un+1, vn+1 a wn+1 značí vrcholy u1, v1 a w1. 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 včetně v definici použitých pojmů.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že každý rovinný graf, který neobsahuje kružnici délky nejvýše
pět, má vrchol stupně nejvýše dva.