Teorie grafů – podzim 2021 – 3. termín
1. (10 bodů) Na následujícím grafu předveďte běh Dijkstrova algoritmu s počátečním
vrcholem E. Vyznačte algoritmem získaný strom nejkratších cest.
A 2
0
B
2
2
1
0
C
1
D 1
3
2
E
4
1
F
2
1
G
1
H
0
I
2. (10 bodů) Určete chromatický polynom grafu K2,3.
3. (5 bodů) Dejte příklad 3-regulárního grafu s osmi vrcholy a jeho dvou vrcholů u
a v takových, že d(u, v) = 3 a existují právě čtyři nejkratší cesty z u do v. Pokud
takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad eulerovského grafu G se sedmi vrcholy, který splňuje
χ (G) ≥ 5 a χ(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého grafu se šesti vrcholy, který má až na izomorfismus
právě tři kostry. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která nezáporná celá čísla x a y je posloupnost
(x, x, x, x + 2, y, y + 2, y + 2, y + 2, y + 2)
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 se šesti vrcholy a pěti
hranami, které mají právě jeden bod artikulace.
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 celé číslo a nechť G je obyčejný graf, který vznikne
z grafu Kn provedením dělení jedné jeho hrany. Určete hranovou a vrcholovou
souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či
hamiltonovský.
11. (5 bodů) Definujte vrcholovou a hranovou souvislost grafu κ a κ .
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že v každém n-souvislém grafu, který má právě 2n vrcholů,
existuje perfektní párování.