Teorie grafů — podzim 2013 — 4. termín
1. (10 bodů) Následující graf vyjadřuje pravděpodobnost přechodu systému mezi stavy A, B, C a D během jednoho kroku. Určete, ve kterém stavu je třeba práci systému zahájit, aby pravděpodobnost, že po čtyřech krocích bude ve stavu D, byla co největší.
3
2. (10 bodů) Nalezněte největší párování v následujícím grafu. Svoje tvrzení zdůvodněte.
3. (5 bodů) Dejte příklad grafu G se šesti vrcholy, který splňuje = 3 a přitom pro každý graf H, který vznikne přidáním jedné hrany ke G, platí x{H) = 4. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad grafu G se sedmi vrcholy, který splňuje k(G) = x'{G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad ohodnoceného souvislého grafu s pěti vrcholy, který obsahuje právě jednu zápornou hranu, a jeho dvou vrcholů u a, v takových, že při výpočtu nejkratších cest z u dává Dijkstrův algoritmus správný výsledek, zatímco při výpočtu nejkratších cest z v nikoli. 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,2,x,4,í/,x + 4)
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í souvislé grafy G se šesti vrcholy, které mají právě dva maximální 2-souvislé podgrafy.
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élek n, n a 2n, přičemž první cyklus má vrcholy u±,... ,un, druhý Vi,..., vn a třetí Wi,..., W2n (vrcholy leží na cyklech v uvedeném pořadí). Tyto cykly jsou spojeny hranami UíWí a ViWi+n 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 tok v síti a jeho velikost.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že libovolný regulární rovinný eulerovský graf G splňuje X'(G) < 5.