Teorie grafů – podzim 2017 – 2. termín
1. (10 bodů) Následující graf vyjadřuje pravděpodobnost přechodu systému mezi
stavy A, B, C a D během jednoho kroku. Určete, ve kterých stavech je možné
práci systému zahájit, aby pravděpodobnost, že po čtyřech krocích bude ve stavu
A, byla vyšší, než že bude ve stavu C.
A
1
2

1
4
//
1
4

B
3
4
oo
1
4

C
1
2
OO
1
2
// D
1
4oo
1
2
__
1
4
QQ
2. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
2
•
2
2 4
2
•
3
3 •
3
3
• 1
• 4
•
3. (5 bodů) Dejte příklad grafu s osmi vrcholy, který je hranově 2-souvislý, není
eulerovský a každý jeho vrchol stupně většího než dva je bodem artikulace. Pokud
takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad souvislého nerovinného grafu, který má 9 vrcholů a 11
hran. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G, který má šest vrcholů, splňuje χ(G) = 4 a přitom
neobsahuje podgraf izomorfní K4. 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, 2, 2, 3, 4, 5, x, 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í obyčejné grafy G, které mají
šest vrcholů, nejsou hamiltonovské a splňují κ(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 je kladné celé číslo a G = (V, E) je obyčejný graf, kde V =
{ ai, bi | i = 1, . . . , n } ∪ {c, d} a E = { aibi, aic, bic, aid, bid | 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 větu o největších párováních a o vrcholových pokrytích
v bipartitních grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Dokažte, že každý rovinný graf o n vrcholech obsahuje více než n/13
vrcholů stejného stupně.