Teorie grafů – podzim 2019 – 1. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
2
•
2
2 4
1
•
1
5 •
3
2
• 5
• 4
•
2. (10 bodů) Určete chromatický polynom grafu
• • •
• • •
3. (5 bodů) Dejte příklad eulerovského grafu G se sedmi vrcholy, který splňuje
κ(G) = 3 a χ(G) = 4. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad hranově 2-souvislého bipartitního grafu, který má následující
blokový strom. Pokud takový graf neexistuje, zdůvodněte proč.
• • •
• •
• • •
.
5. (5 bodů) Dejte příklad souvislého grafu se šesti vrcholy, který není hamiltonovský
a přitom jeho střed obsahuje všechny jeho vrcholy. 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 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élek n a 2n, přičemž první cyklus má vrcholy u1, . . . , un a
druhý v1, . . . , v2n (vrcholy leží na cyklech v uvedeném pořadí). Tyto cykly jsou
spojeny hranami uivi a uivi+n pro i ∈ {1, . . . , n}. Určete hranovou a vrcholovou
souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či
hamiltonovský.
11. (5 bodů) Definujte rezervní polocestu a její rezervu.
12. (5 bodů) Formulujte Tutteho větu o perfektním párování a vysvětlete v ní použité
pojmy.
13. (10 bodů) Dokažte, že pro každý regulární rovinný graf G s lichým počtem vrcholů
platí χ (G) ≤ 5.