Teorie grafů – podzim 2014 – 2. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
€€€€€€€€€€€€€ 2
•
2
♠♠♠♠♠♠♠♠♠♠♠♠♠♠
2
✍✍✍✍✍✍✍✍✍✍✍✍✍
4
2
❄❄❄❄❄❄❄❄
•
3 ❄❄❄❄❄❄❄❄❄
5
❖❖❖❖❖❖❖❖❖❖❖❖❖❖ •
3
✂✂✂✂✂✂✂✂✂
2
• 5
• 4
•
2. (10 bodů) Určete chromatický polynom grafu
•
❄❄❄❄❄❄❄❄ •
❀❀❀❀❀❀❀❀ •
• •
3. (5 bodů) Dejte příklad nakreslení nějakého grafu s pěti vrcholy v rovině, které
má právě sedm stěn. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který splňuje κ(G) = 1 a
κ′
(G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který splňuje χ(G) = χ′
(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
(2, 3, 4, 4, 5, x, 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í souvislé grafy se šesti vrcholy,
jejichž blokový strom má právě pět vrcholů.
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 ≥ 3 je celé číslo a G je obyčejný graf s n + 1 vrcholy
u1, . . . , un, v, přičemž tyto vrcholy jsou spojeny hranami uiv pro všechny indexy
i ∈ {1, . . . , n} a uiuj pro i, j ∈ {1, . . . , n} taková, že číslo i − j je kongruentní
1 nebo 2 modulo 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 řez sítě a rezervní polocestu.
12. (5 bodů) Formulujte větu o struktuře 2-souvislých grafů a vysvětlete všechny
pojmy, které se v ní vyskytují.
13. (10 bodů) Nechť X značí množinu všech konečných podmnožin množiny N. Dokažte,
že pro každou ekvivalenci konečného indexu na X existuje třída rozkladu
taková, že obsahuje dvě disjunktní množiny i jejich sjednocení.