Teorie grafů – podzim 2022 – 3. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
3
•
2
2 4
2
•
1
5 •
3
2
• 5
• 4
•
2. (10 bodů) Určete chromatický polynom grafu
•
• • • •
3. (5 bodů) Dejte příklad grafu G se sedmi vrcholy takového, že platí κ(G) = 2 a
přidáme-li ke G libovolnou hranu mezi jeho vrcholy, tak se hodnota κ(G) změní.
Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G s osmi vrcholy, který nemá vrchol stupně 1 a má
právě jedno perfektní párování. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který má 17 hran a splňuje
rovnost χ(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, 2x)
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é bipartitní grafy se
sedmi vrcholy, jejichž blokový strom má sedm vrcholů.
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 ≥ 2 je přirozené číslo a G je obyčejný graf s 2n + 2 vrcholy
u1, . . . , u2n, v, w, přičemž vrcholy u1, . . . , u2n (v tomto pořadí) tvoří kružnici a navíc
graf G obsahuje hrany uiui+n, vu2i−1 a wu2i, 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 Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že má-li souvislý obyčejný graf G právě čtyři vrcholy lichého
stupně, tak v něm existují dva tahy takové, že každá hrana grafu G leží na právě
jednom z nich.