Teorie grafů – podzim 2015 – 4. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
€€€€€€€€€€€€€ 2
•
3
♠♠♠♠♠♠♠♠♠♠♠♠♠♠
1
✍✍✍✍✍✍✍✍✍✍✍✍✍
4
2
❄❄❄❄❄❄❄❄
•
1 ❄❄❄❄❄❄❄❄❄
5
❖❖❖❖❖❖❖❖❖❖❖❖❖❖ •
3
✂✂✂✂✂✂✂✂✂
2
• 5
• 4
•
2. (10 bodů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok
největší velikosti.
síť: • 6 GG
3

•
3
ÒÒ☎☎☎☎☎☎☎☎☎☎
5 GG•
3

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

•
0
ÒÒ☎☎☎☎☎☎☎☎☎☎
2 GG•
0

2
))❀❀❀❀❀❀❀❀❀
'&%$!"#s
6
11❅❅❅❅❅❅❅❅❅
1 GG
4
ee✂✂✂✂✂✂✂✂✂✂
•
2

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

'&%$!"#t '&%$!"#s
2
11❅❅❅❅❅❅❅❅❅
1 GG
3
ee✂✂✂✂✂✂✂✂✂✂
•
1

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

'&%$!"#t
• 6
GG•
3
””❂❂❂❂❂❂❂❂❂❂
3
GG•
6
cc⑧⑧⑧⑧⑧⑧⑧⑧⑧ • 3
GG•
0
””❂❂❂❂❂❂❂❂❂❂
3
GG•
3
cc⑧⑧⑧⑧⑧⑧⑧⑧⑧
3. (5 bodů) Dejte příklad grafu G s devíti vrcholy, který splňuje κ(G) = χ′
(G) = 5.
Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu s deseti vrcholy, v němž nějaká nejdelší cesta neobsahuje
žádný vrchol středu. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který není hamiltonovský a
splňuje κ(G) = 2 a χ′
(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 (2, 2, x, y, 5, 6, 6, 6)
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) = 4, κ(G) = 1 a κ′
(G) = 2.
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 ≥ 1 je přirozené číslo a G je obyčejný graf s 3n vrcholy ui, vi
a wi, pro i = 1, . . . , n, a s množinou hran
E = { uiuj, vivj, wiwj | i, j ∈ {1, . . . , n}, i = j } ∪ { uivj, viwj | i, 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 izomorfismus grafů.
12. (5 bodů) Formulujte větu o struktuře 2-souvislých grafů.
13. (10 bodů) Dokažte, že pro libovolné přirozené číslo n ≥ 2 platí, že každý n-souvislý
graf s alespoň 2n vrcholy obsahuje kružnici délky alespoň 2n.