Teorie grafů – podzim 2018 – 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ů) 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, jaká je pravděpodobnost, že se
systém po čtyřech krocích bude nacházet ve stavu A, začíná-li v každém stavu se
stejnou pravděpodobností.
A
1
2

1
4
//
1
4

B
3
4oo
1
4

C
1
4
OO
3
4
// D
1
2
oo
1
4
__
1
4
QQ
3. (5 bodů) Dejte příklad rovinného bipartitního grafu G s devíti vrcholy, který
splňuje κ (G) = 3 a χ (G) = 5. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad eulerovského grafu, který má následující blokový strom.
Pokud takový graf neexistuje, zdůvodněte proč.
• • •
• • • •
• • •
.
5. (5 bodů) Dejte příklad 2-souvislého grafu s pěti vrcholy, který není hamiltonovský.
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 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 ≥ 2 je přirozené číslo a nechť G je obyčejný graf s n2
vrcholy
ui,j, pro i, j = 1, . . . , n, a s hranami ui,jui,j+1 a ui,nui,1, pro i = 1, . . . , n, j =
1, . . . , n − 1, a ui,jui+1,j a un,ju1,j, pro i = 1, . . . , n − 1, j = 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 obyčejný graf a izomorfismus obyčejných grafů.
12. (5 bodů) Formulujte Tutteho větu o perfektním párování a vysvětlete v ní použité
pojmy.
13. (10 bodů) Pro každé přirozené číslo n dokažte, že pokud v každém podgrafu
grafu G = (V, E) existuje vrchol stupně nejvýše 2n
− 1, tak existují podmnožiny
E1, . . . , En ⊆ E takové, že E = E1 ∪ · · · ∪ En a grafy (V, E1), . . . , (V, En) jsou
bipartitní.