Teorie grafů — podzim 2011 — 4. termín
1. (10 bodů) Určete počet sledů délky 8 z vrcholu A do každého vrcholu grafu
A-
3 6 3
3. (5 bodů) Dejte příklad grafu G, který splňuje = 4 a x'{G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G, který má šest vrcholů a splňuje x'{G) = 4 a k(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého grafu, který obsahuje právě dvě kružnice a má stejně bodů artikulace jako mostů. Pokud takový graf neexistuje, zdůvodněte proč.
6. (2x5 bodů) Dejte příklad grafu G se skóre (2, 2, 2,3, 3, 3, 3,4), který splňuje
a) k'(G) = 1.
b) k'(G) = 2.
7. (10 bodů) Najděte všechny vzájemně neizomorfní eulerovské 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 je přirozené číslo a G je graf tvořený dvěma cestami délky n a dvěma vrcholy u a w, přičemž u i w jsou spojeny hranami právě se všemi vrcholy obou cest. Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte podgraf a indukovaný podgraf obyčejného grafu.
12. (5 bodů) Formulujte Tutteho větu o perfektním párování a vysvětlete v ní použité pojmy.
13. (10 bodů) Nechť n je liché přirozené číslo. Dokažte, že pro graf G vzniklý odebráním nejvýše       hran z grafu Kn platí x'(G) = n.