Teorie grafů – podzim 2014 – 1. termín
1. (10 bodů) Určete počet sledů délky osm z vrcholu D do vrcholu E v grafu
A B
⑦⑦⑦⑦⑦⑦⑦⑦
C
⑦⑦⑦⑦⑦⑦⑦⑦
D E
2. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami
hran a dvou vrcholů a svoje rozhodnutí zdůvodněte.
• 6 GG/.-,()*+5
3

6 GG•
6
''✽✽✽✽✽✽✽✽✽
'&%$!"#s
9
))❀❀❀❀❀❀❀❀
7 GG
4
ff✝✝✝✝✝✝✝✝✝
•
2
yy
3 GG/.-,()*+5
3
yy
6 GG
3
ÑÑ✄✄✄✄✄✄✄✄ • 7 GG
3

2
yy
'&%$!"#t
•
1
ee✄✄✄✄✄✄✄✄
7
GG•
3
yy
3
ee✄✄✄✄✄✄✄✄✄✄
3
GG•
5
ee✄✄✄✄✄✄✄✄
3. (5 bodů) Dejte příklad grafu s osmi vrcholy, který má právě 27 koster. Pokud
takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad souvislého grafu se šesti vrcholy, který má právě 12 hran
a dva bloky. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G, který má sedm vrcholů a splňuje κ′
(G) = 3
a κ(G) = 2. 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, 2, 2, 3, 3, x, y, 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ů) Nechť d ≥ 1 je celé číslo. Najděte všechny vzájemně neizomorfní
d-regulární grafy G, které mají deset vrcholů a splňují χ(G) > d.
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.
•
✴✴✴✴✴✴✴✴✴✴✴✴✴
♠♠♠♠♠♠♠♠♠♠♠♠♠♠ • •
ttttttttttttttttttttt
✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐✐
•
❇❇❇❇❇❇❇❇❇ •
€€€€€€€€€€€€€ •
❄❄❄❄❄❄❄❄
⑤⑤⑤⑤⑤⑤⑤⑤⑤ •
• •
10. (10 bodů) Nechť n ≥ 2 je celé číslo a G je obyčejný graf tvořený dvěma disjunktními
kružnicemi délky 2n s vrcholy u1, . . . , u2n a v1, . . . , v2n (v tomto pořadí),
přičemž tyto kružnice jsou spojeny právě hranami ukvℓ pro indexy k a ℓ splňující
k ≡ ℓ (mod 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 obsahuje-li 3-souvislý graf kružnici liché délky, potom
obsahuje takové kružnice aspoň čtyři.