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

C
yy bb
GG Doo
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
ÐÐ
2 GG•
1

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
0
’’
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, jehož blokový strom má dvouvrcholový
střed. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad obyčejného grafu, který má právě tři izomorfismy na sebe.
Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G s osmi vrcholy, který není hamiltonovský a platí
pro něj κ(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
(x, x, 3, 5, 5, 6, 7, y, 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 takové,
že odstraněním libovolné jejich hrany se sníží hodnota χ(G).
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 tvořený n disjunktními
cykly délky n, přičemž i-tý cyklus má vrcholy vi,1, . . . , vi,n (vrcholy leží na
cyklech v uvedeném pořadí). Tyto cykly jsou spojeny pro všechna j ∈ {1, . . . , n}
hranami vi,jvi+1,j pro i ∈ {1, . . . , n − 1} a vn,jv1,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 pojem vrcholové souvislosti grafu a vysvětlete v definici použité
pojmy.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pro přirozená čísla m a n a graf G = (V, E) existuje
rozklad množiny hran E = E1 ∪E2 takový, že χ(V, E1) ≤ m a χ(V, E2) ≤ n, právě
tehdy, když χ(G) ≤ m · n.