Teorie grafů – podzim 2024 – 5. termín
1. (10 bodů) Určete chromatický polynom grafu
• • •
• • •
2. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
1
1
•
3 2
3
•
3
4 2
1
•
2
4 •
3 2
• 2
• 2
•
3. (5 bodů) Dejte příklad souvislého grafu s dvanácti vrcholy takového, že jeho
blokový strom má perfektní párování. Pokud takový graf neexistuje, zdůvodněte
proč.
4. (5 bodů) Dejte příklad obyčejného grafu G s devíti vrcholy, který je eulerovský
a splňuje κ(G) = χ(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad ohodnoceného orientovaného grafu G a jeho vrcholu v
takového, že Dijkstrův algoritmus při spuštění na grafu G s počátečním vrcholem v
může dát správný i chybný výsledek. 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 obyčejné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 sedmi vrcholy, které
splňují χ(G) > χ (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 ≥ 1 je přirozené číslo a G je obyčejný graf s 3n vrcholy ui, vi
a wi, pro i = 1, . . . , n, a s množinou hran
E = { uiuj, vivj, wiwj, uivj, viwj | i, j ∈ {1, . . . , n}, i = j }.
Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické
číslo, zda je G eulerovský a zda je hamiltonovský.
11. (5 bodů) Definujte rezervní polocestu a její rezervu.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že každý 2-souvislý graf o n vrcholech, který není izomorfní
grafu Cn, má alespoň 3n − 4 koster.