Teorie grafů — podzim 2012 — 4. termín
1. (10 bodů) Určete počet sledů délky osm z vrcholu A do vrcholu A v grafu
A-B-C
D-E
2. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami hran a dvou vrcholů a svoje rozhodnutí zdůvodněte.
7
3. (5 bodů) Dejte příklad grafu se šesti vrcholy, který má právě devět koster. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad eulerovského grafu se sedmi vrcholy, který obsahuje indukovaný podgraf izomorfní cyklu Cq. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad rovinného grafu G, který má osm vrcholů a splňuje = 2 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 (1,1,1,1, x, 4, 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í grafy G, které splňují = 3 a k'(G) = 2 a mají právě osm hran a jeden bod artikulace.
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 > 0 je celé číslo a G je obyčejný graf tvořený třemi disjunktními cestami délky n a dvěma dalšími vrcholy, které jsou oba spojeny hranami se všemi vrcholy grafu. Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte blok grafu.
12. (5 bodů) Formulujte větu o největším párování v bipartitních grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Nechť k a, n jsou přirozená čísla, přičemž n je liché. Dokažte, že pro libovolný graf G, který má n vrcholů a kn hran, platí x'{G) > 2k + 1.