Teorie grafů — podzim 2012 — 1. termín
1. (10 bodů) Určete počet sledů v následujícím orientovaném grafu, které začínají ve vrcholu A a mají délku osm.
A^^B
2. (10 bodů) Pomocí algoritmu Edmondse a Karpa upravte následující tok na tok největší velikosti.
5 2 2 2
3. (5 bodů) Dejte příklad 2-souvislého grafu, který má šest vrcholů, je eulerovský, ale není hamiltonovský. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu se čtyřmi vrcholy, který má až na izomorfismus právě čtyři indukované podgrafy se třemi vrcholy. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G s pěti vrcholy, který splňuje = 3, ale přitom pro libovolný graf H vzniklý přidáním jediné hrany ke G platí x{H) = 4. 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, x, x, 4, 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í hranově 2-souvislé grafy G, které splňují = 4 a mají právě dvanáct hran 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 > 3 je přirozené číslo a G je obyčejný graf tvořený třemi disjunktními cykly délky n s vrcholy u1}... ,un, respektive v1}... ,vn, respektive Wi,... ,wn (vrcholy leží na cyklech v uvedeném pořadí), přičemž tyto cykly jsou spojeny hranami UíVí a VíWí 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 pojem vrcholové souvislosti grafu a vysvětlete v definici použité pojmy.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že střed blokového stromu libovolného grafu obsahuje jediný vrchol.