Teorie grafů – podzim 2017 – 4. 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.
v2
3
~~
2

5
v1
1
>>
4
//
3
v5
1

5
OO
1
// v3
1
``
2oo
6
~~
v4
2
``
6
OO
2. (10 bodů) Určete chromatický polynom grafu
• • •
• • •
3. (5 bodů) Dejte příklad 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č.
4. (5 bodů) Dejte příklad souvislého d-regulárního grafu G se sedmi vrcholy, který
splňuje κ(G) < d. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G s deseti vrcholy, který splňuje κ(G) = 7 a χ(G) =
3. 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 + 1, 5, 5, 5, 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 se šesti vrcholy,
které mají počet bodů artikulace o 2 menší než počet bloků.
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 = (V, E) je obyčejný graf, kde
V = {u, v} ∪ { wi,j | i ∈ {1, 2, 3}, j ∈ {1, . . . , n} },
E = { uwi,1, vwi,n | i ∈ {1, 2, 3} }
∪ { wi,jwk,j+1 | i, k ∈ {1, 2, 3}, j ∈ {1, . . . , n − 1} }.
Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické
číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte tok v síti a jeho velikost.
12. (5 bodů) Formulujte Mengerovu větu o vrcholové souvislosti obyčejných grafů a
vysvětlete v ní použité pojmy.
13. (10 bodů) Dokažte, že v každém n-souvislém grafu, který má právě 2n vrcholů,
existuje perfektní párování.