Teorie grafů – podzim 2014 – 3. termín
1. (10 bodů) Určete počet sledů v následujícím orientovaném grafu, které končí ve
vrcholu D a mají délku osm.
A GG
22❅❅❅❅❅❅❅❅ Boo

C
yy bb⑦⑦⑦⑦⑦⑦⑦⑦
GG Doo
2. (10 bodů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok
největší velikosti.
síť: •
3
ÐÐ✂✂✂✂✂✂✂✂✂✂✂
5 GG•
3

1
))❀❀❀❀❀❀❀❀❀ tok: •
1
ÐÐ✂✂✂✂✂✂✂✂✂✂✂
2 GG•
1

1
))❀❀❀❀❀❀❀❀❀
'&%$!"#s
6
44❋❋❋❋❋❋❋❋❋❋ 1
GG
4
UU♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦
•
2

3 GG• 3 GG
3
’’✿✿✿✿✿✿✿✿✿✿
3
ÐÐ✁✁✁✁✁✁✁✁✁✁
4

'&%$!"#t '&%$!"#s
2
55●●●●●●●●●● 1
GG
3
UU♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
•
1

1 GG• 2 GG
0
’’✿✿✿✿✿✿✿✿✿✿
0
ÐÐ✁✁✁✁✁✁✁✁✁✁
0

'&%$!"#t
• 6
GG•
3
••❅❅❅❅❅❅❅❅❅❅
3
GG•
7
cc⑧⑧⑧⑧⑧⑧⑧⑧⑧ • 3
GG•
0
••❅❅❅❅❅❅❅❅❅❅
3
GG•
3
cc⑧⑧⑧⑧⑧⑧⑧⑧⑧
3. (5 bodů) Dejte příklad regulárního grafu, který má právě devět vrcholů a jeden
most. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu se sedmi vrcholy, který má právě osm koster. Pokud
takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se šesti vrcholy, pro který platí χ(G) = 3 a
κ(G) = 4. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(x, x, 3, 5, 5, 6, 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 šesti vrcholy, které
splňují χ′
(G) = κ′
(G) ≥ 1.
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 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í) se spojenými
protilehlými vrcholy, tj. s hranami ukuk+n a vkvk+n pro k ∈ {1, . . . , n}, přičemž
tyto kružnice jsou spojeny právě hranami ukvk pro všechna k ∈ {1, . . . , 2n}.
Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické
číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte pojem vrcholové souvislosti grafu a vysvětlete v definici použité
pojmy.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že každé rovinné nakreslení regulárního 3-souvislého grafu
s lichým počtem vrcholů má lichý počet stěn.