Teorie grafů — podzim 2011 — 2. termín
1. (10 bodů) Použitím některého algoritmu pracujícího s maticovou reprezentací grafu určete vzdálenosti mezi všemi dvojicemi vrcholů následujícího grafu. Přitom vrcholy v matici reprezentujte v pořadí v±,      v%, v±, v&.
v2
V3
2. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami hran a jednoho vrcholu a svoje rozhodnutí zdůvodněte.
10 3
3. (5 bodů) Dejte příklad grafu G, který má právě 10 hran, splňuje = 3 a není rovinný. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 3-souvislého grafu se šesti vrcholy a osmi hranami. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad souvislého grafu, který obsahuje právě tři mosty, dva body artikulace a jednu kružnici. Pokud takový graf neexistuje, zdůvodněte proč.
6. (2x5 bodů) Dejte příklad grafu se skóre (2,2,2,2,3,3,4), který
a) je 2-souvislý.
b) není 2-souvislý.
7. (10 bodů) Najděte všechny vzájemně neizomorfní grafy G, které mají pět vrcholů, nejsou souvislé a splňují x'{G) = 3.
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 graf tvořený dvěma cykly Ui,..., un a v1}..., vn délky n, které jsou spojeny hranami UíVí pro i G {1,..., n}. 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 struktuře 2-souvislých grafů.
13. (10 bodů) Nechť k je přirozené číslo. Dokažte, že pokud hranově fc-souvislý graf G obsahuje bod artikulace, tak platí x'{G) > 2k.