Teorie grafů – podzim 2015 – 2. termín
1. (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/.-,()*+6
3

6 GG•
5
''✽✽✽✽✽✽✽✽✽
'&%$!"#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✄✄✄✄✄✄✄✄
2. (10 bodů) Určete chromatický polynom grafu
•
⑧⑧⑧⑧⑧⑧⑧⑧
❀❀❀❀❀❀❀❀
▼▼▼▼▼▼▼▼▼▼▼▼
• • • •
3. (5 bodů) Dejte příklad souvislého grafu G se šesti vrcholy, který splňuje rovnosti
χ(G) = χ′
(G) = 4 a není hamiltonovský. Pokud takový graf neexistuje, zdůvodněte
proč.
4. (5 bodů) Dejte příklad souvislého grafu G s 12 vrcholy, který splňuje χ(G) = 3
a všechny jeho kostry jsou izomorfní. Pokud takový graf neexistuje, zdůvodněte
proč.
5. (5 bodů) Dejte příklad grafu G se šesti vrcholy, který je eulerovský a splňuje
κ′
(G) = 3. 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, 1, 2, x, 4, y, 2x)
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 s pěti vrcholy takové,
že κ(G) = 1 a každý jejich bod artikulace má jiný stupeň.
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 a nechť G = (V, E) je obyčejný graf s množinou vrcholů
V = {0, . . . , n − 1} × {0, . . . , n − 1} a množinou hran
E = { {(i, j), (i, (j + 1) mod n)}, {(i, j), ((i + 1) mod n, j)} | (i, j) ∈ V } .
Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické
číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte blokový strom včetně v definici použitých pojmů.
12. (5 bodů) Formulujte Tutteho větu o perfektním párování a vysvětlete v ní použité
pojmy.
13. (10 bodů) Dokažte, že v libovolném stromě každá nejdelší cesta obsahuje všechny
vrcholy středu.