Teorie grafů — podzim 2011 — vzorová písemka
1. (10 bodů) Nalezněte největší párování v následujícím grafu. Svoje tvrzení zdůvodněte.
2. (10 bodů) Určete počet sledů délky 16 mezi každou dvojicí vrcholů v grafu
3. (5 bodů) Dejte příklad grafu G, který má právě 6 vrcholů, 11 hran a splňuje k(G) = 1. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad 2-souvislého grafu, který obsahuje právě 2 kružnice. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad neúplného 3-souvislého grafu, který odebráním libovolné hrany přestane být 3-souvislý. Pokud takový graf neexistuje, zdůvodněte proč.
6. (2x5 bodů) Dejte příklad grafu G se skóre (2,2,2,3,3,4,4), který splňuje
a) X(G) = 3.
b) X(G) = 4.
7. (10 bodů) Najděte všechny vzájemně neizomorfní grafy, které mají právě šest vrcholů, jeden most a dva body 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 > 2 je přirozené číslo a G je graf tvořený cyklem délky 2n s vrcholy v1}... ,v2n a dvěma vrcholy u a w, přičemž u je spojen hranou právě s vrcholy v i pro i liché a w je spojen hranou právě s vrcholy v i pro i sudé. Určete hranovou a vrcholovou souvislost G, jeho hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte hranovou souvislost grafu a vysvětlete v definici použité pojmy.
12. (5 bodů) Formulujte Mengerovu větu o lokální vrcholové souvislosti v orientovaných grafech a vysvětlete v ní použité pojmy.
13. (10 bodů) Dokažte, že má-li hranově 2-souvislý graf s n vrcholy b bloků, potom má alespoň n + b — 1 hran.