Teorie grafů – podzim 2023 – 2. termín
1. (10 bodů) Nalezněte největší párování v následujícím grafu. Svoje tvrzení zdů-
vodněte.
• • • • • • • •
• • • • • • • •
2. (10 bodů) Určete chromatický polynom grafu
• • •
• • •
3. (5 bodů) Dejte příklad 3-souvislého bipartitního rovinného eulerovského obyčejného
grafu s 12 vrcholy. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad obyčejného grafu s 10 vrcholy, který má právě tři izomorfismy
na sebe. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad obyčejného grafu G s osmi vrcholy, který má právě dvě
perfektní párování a splňuje rovnosti κ(G) = 1, κ (G) = 2 a χ (G) = 7. Pokud
takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(2, 3, 4, 4, 5, x, 7, y, y)
skórem nějakého obyčejného grafu, a svoje rozhodnutí zdůvodněte. Pro všechny
takové hodnoty x a y dejte příklad obyčejného grafu s tímto skóre.
7. (10 bodů) Najděte všechny vzájemně neizomorfní souvislé obyčejné grafy G
s osmi hranami, které mají právě 16 koster.
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 s 2n vrcholy ui, vi,
pro i = 1, . . . , n, a hranami uivi, uiui+1, uivi+1, viui+1 a vivi+1, pro i = 1, . . . , n, kde
un+1 = u1 a vn+1 = v1. Určete hranovou a vrcholovou souvislost G, jeho hranové
a vrcholové chromatické číslo a zda je G eulerovský nebo hamiltonovský.
11. (5 bodů) Definujte blokový strom souvislého grafu, včetně v definici použitých
pojmů.
12. (5 bodů) Formulujte věty o struktuře 2-souvislých a 3-souvislých grafů.
13. (10 bodů) Pro každé přirozené číslo k ≥ 2 dokažte, že je-li G neúplný graf,
který splňuje κ(G) ≤ k − 2, a α řádné k-obarvení grafu G, potom existuje řádné
k-obarvení grafu G, které se od α liší nejen permutací barev.