Teorie grafů — podzim 2011 — 5. termín
1. (10 bodů) Předveďte běh Dijkstrova algoritmu na následujícím grafu, kde počáteční vrchol je označen s.
3. (5 bodů) Dejte příklad grafu G, který má šest vrcholů a splňuje k(G) = 2 a x{G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G se šesti vrcholy a jedenácti hranami, který splňuje k(G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad eulerovského grafu G, který není regulární a splňuje x'{G) = 5 a k'(G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
6. (2x5 bodů) Dejte příklad grafu se skóre (2,2,2,3,3,4), který
a) je hamiltonovský.
b) není hamiltonovský.
7. (10 bodů) Najděte všechny vzájemně neizomorfní souvislé grafy, které nejsou bipartitní, mají právě šest vrcholů, šest hran a stejně mostů jako bodů artikulace.
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí zdůvodněte.
2. (10 bodů) Určete chromatický polynom grafu
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 nezáporné celé číslo a G je graf tvořený dvěma cestami délky n, přičemž každý vrchol jedné cesty je spojen hranou s každým vrcholem druhé cesty. Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte tok v síti a jeho velikost.
12. (5 bodů) Formulujte Mengerovu větu o hranové souvislosti obyčejných grafů a vysvětlete v ní použité pojmy.
13. (10 bodů) Nechť d G N. Dokažte, že pokud G je cř-regulární graf o lichém počtu vrcholů, tak x'{G) = d + 1.