Teorie grafů — podzim 2013 — 1. termín
1. (10 bodů) Nalezněte všechny kostry nej menší váhy v grafu
1 2
1
2. (10 bodů) Určete chromatický polynom grafu
3. (5 bodů) Dejte příklad nakreslení nějakého hranově 2-souvislého grafu v rovině, v němž některý vrchol stupně šest sousedí s právě čtyřmi stěnami. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G se šesti vrcholy, který splňuje k(G) = 1 a má právě tři indukované podgrafy, které jsou cykly. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který splňuje = 2, x'{G) = 5 a k(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
(l,l,l,l,2,x,4,y,2x)
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 G se sedmi vrcholy, které splňují = 3 a x'{G) = 4 a mají právě tři mosty.
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 přirozené číslo a G je obyčejný graf tvořený třemi cykly délky n s jedním společným vrcholem x, přičemž vrcholy prvního cyklu jsou x,Ui,..., itn_i, druhého cyklu x, v1}..., -un-i a třetího cyklu x, w1}..., wn_i (vrcholy leží na cyklech v uvedeném pořadí). Tyto cykly jsou dále spojeny hranami UíVí a VíWí pro i G {1,... ,n — 1}. 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ů.
13. (10 bodů) Dokažte, že libovolný eulerovský graf G, který splňuje k'(G) > k(G), přičemž k(G) je sudé, má alespoň k(G) + 6 vrcholů.