Teorie grafů – podzim 2020 – 3. termín
1. (10 bodů) Závodu, který je určen pro jednotlivce a smíšené páry, se hodlá zúčastnit
devět chlapců označených písmeny A až I a devět dívek označených písmeny
α až ι. Následující tabulka udává pro všechny chlapce, se kterými dívkami mohou
vytvořit tým.
A δ, ζ B δ, ζ, ι C α, β, ε, η, ϑ D α, ι E δ, ι F γ, ε, ϑ, ι
G α, δ, ι H δ, ζ I β, γ, η, ϑ, ι
Aktuálně platí nařízení dovolující pořádat pouze soutěže, kterých se účastní nejvýše
deset týmů, bez ohledu na počet členů týmu. Rozhodněte, zda je možné, aby
se při dodržení tohoto nařízení závodu zúčastnili všichni zájemci. Svoje rozhodnutí
zdůvodněte.
2. (10 bodů) Určete počet uzavřených sledů délky 8 v grafu
A B
C D
3. (5 bodů) Dejte příklad souvislého grafu s devíti vrcholy, který má stejně bloků
jako koster. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 3-souvislého grafu G se šesti vrcholy, který splňuje χ(G) =
3 a χ (G) = 5. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který není hamiltonovský 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, 1, 2, x, 4, y, x + 3)
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 s osmi vrcholy, které
splňují κ (G) = κ(G) + 2.
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ý dvěma
disjunktními cykly délky n s vrcholy u1, . . . , un a v1, . . . , vn (vrcholy leží na cyklech
v uvedeném pořadí). Tyto cykly jsou spolu spojeny hranami uivi−1 a uivi+1 pro
i ∈ {1, . . . , n} (přitom v0 značí vrchol vn a vn+1 značí vrchol v1). Určete hranovou
a vrcholovou souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G
eulerovský či hamiltonovský.
11. (5 bodů) Definujte střed grafu.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že pro libovolné přirozené číslo n platí, že má-li každý vrchol
obyčejného grafu G o 2n vrcholech stupeň alespoň n, tak κ (G) je rovno nejmenšímu
stupni vrcholu v G.