Teorie grafů – podzim 2012 – 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, s jakou pravděpodobností bude
systém začínající ve stavu A ve kterém stavu po čtyřech krocích.
A
1
2

1
2
// B
1
2
oo
1
2

C
1
2
OO
1
2
??~~~~~~~~~~~~~~~~~
D1
4
oo
1
2
__ddddddddddddddddd
1
4
QQ
2. (10 bodů) Určete chromatický polynom grafu
•
YYYYYYYY •
££££££££ •
• •
3. (5 bodů) Dejte příklad regulárního grafu, který má pět vrcholů, je eulerovský,
ale není hamiltonovský. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad souvislého grafu s pěti vrcholy, který má až na izomorfismus
právě čtyři indukované podgrafy se třemi vrcholy. Pokud takový graf neexistuje,
zdůvodněte proč.
5. (5 bodů) Dejte příklad hranově 2-souvislého grafu, který má sedm vrcholů a nemá
kostru, která je cesta. 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, x, 4, 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í souvislé grafy G se šesti vrcholy,
které mají právě tolik mostů, kolik je hodnota χ(G).
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí
zdůvodněte.
• • •
¢¢¢¢¢¢¢¢¢
WWWWWWWW •
¥¥¥¥¥¥¥¥
WWWWWWWW
•
WWWWWWWW •
¥¥¥¥¥¥¥¥ •
`````````
vvvvvvvvvvvv • • •
¥¥¥¥¥¥¥¥
ssssssssssss
• • • •
• •
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.
•
mmmmmmmmmmmmmm
cccccccc •
iiiiiiiiiiiiiiiiiii
nnnnnnnnnnnnn

YYYYYYYY •
jjjjjjjjjjjjjjjjjj
pppppppppppp
££££££££
•
………………………………………………… • •
cccccccc • •
££££££££
•
10. (10 bodů) Nechť n ≥ 2 je přirozené číslo a G je obyčejný graf tvořený třemi disjunktními
cestami délky n−1 s vrcholy u1, . . . , un, respektive v1, . . . , vn, respektive
w1, . . . , wn (vrcholy leží na cestách v uvedeném pořadí), přičemž tyto cesty jsou
spojeny hranami uivi, uiwi a viwi 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 větu o struktuře 2-souvislých grafů.
13. (10 bodů) Dokažte, že je-li G souvislý graf, který obsahuje bod artikulace stupně 3,
potom κ′
(G) = 1.