Teorie grafů — podzim 2013 — 2. termín
1. (10 bodů) Určete počet sledů délky osm z vrcholu A do vrcholu B v grafu
D-E
2. (10 bodů) Určete největší velikost toku v následující síti s danými kapacitami hran a dvou vrcholů a svoje rozhodnutí zdůvodněte.
7
3. (5 bodů) Dejte příklad eulerovského grafu G se sedmi vrcholy, který splňuje k(G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad souvislého grafu G se sedmi vrcholy, který splňuje = 4 a x'{G) = 3. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad nezáporně ohodnoceného souvislého grafu s pěti vrcholy a jeho dvou vrcholů u a, v takových, že při výpočtu nejkratších cest z vrcholu u pomocí Dijkstrova algoritmu se aktuální hodnota spočítaná pro vrchol v mění v každém kroku. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost
(l,l,l,x,4,y,y,y + 1)
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í grafy G se sedmi vrcholy, které splňují k'(G) = 2 a obsahují právě tři kružnice.
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ý dvěma disjunktními cykly délek n a 2n, přičemž první cyklus má vrcholy ui,... ,un a druhý Vi,... ,V2n (vrcholy leží na cyklech v uvedeném pořadí). Tyto cykly jsou spojeny hranami UíVí a UiVi+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 blok grafu.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Nechť G = (V, E) je graf se sudým počtem vrcholů a, v E V jeho vrchol stupně dva takový, že graf G \ v je ^-souvislý. Dokažte, že potom je G hamiltonovský.