Teorie grafů – podzim 2015 – 1. termín
1. (10 bodů) Nalezněte všechny kostry nejmenší váhy v grafu
•
2
1
•
3 2
€€€€€€€€€€€€€ 2
•
3
♠♠♠♠♠♠♠♠♠♠♠♠♠♠
2
✍✍✍✍✍✍✍✍✍✍✍✍✍
4
2
❄❄❄❄❄❄❄❄
•
1 ❄❄❄❄❄❄❄❄❄
5
❖❖❖❖❖❖❖❖❖❖❖❖❖❖ •
3
✂✂✂✂✂✂✂✂✂
2
• 5
• 4
•
2. (10 bodů) Následující graf vyjadřuje pravděpodobnost přechodu systému mezi
stavy A, B, C a D během jednoho kroku. Určete, ve kterém stavu je třeba práci
systému zahájit, aby pravděpodobnost, že se systém ve čtvrtém kroku vrátí do
tohoto stavu, byla co největší.
A
1
2

1
4
//
1
4
❅❅❅❅❅❅❅❅❅❅❅❅❅❅❅❅❅ B
3
4oo
1
4

C
1
2
OO
1
2
// D
1
2oo
1
4
__❅❅❅❅❅❅❅❅❅❅❅❅❅❅❅❅❅
1
4
QQ
3. (5 bodů) Dejte příklad grafu G se šesti vrcholy, který splňuje χ(G) = 3 a má
právě 16 podgrafů, které jsou úplné. Pokud takový graf neexistuje, zdůvodněte
proč.
4. (5 bodů) Dejte příklad 5-souvislého eulerovského rovinného grafu. Pokud takový
graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad hranově 3-souvislého grafu takového, že počet jeho bodů
artikulace je o dva menší než počet jeho bloků. 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, x, 4, 4, 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í 2-souvislé grafy s pěti vrcholy.
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 a nechť G je obyčejný graf vzniklý odebráním dvou hran,
které mají společný vrchol, z grafu Kn. 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 Tutteho větu o perfektním párování a vysvětlete v ní použité
pojmy.
13. (10 bodů) Dokažte, že každý souvislý regulární graf G = (V, E) splňující nerovnost
|V | ≤ 2 · χ(G) je hamiltonovský.