Teorie grafů — podzim 2017 — 3. termín
1. (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 3-regulárního grafu s osmi vrcholy, který není rovinný. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad hamiltonovského a eulerovského grafu se šesti vrcholy a jeho podgrafu, který má také šest vrcholů, je eulerovský, ale není hamiltonovský. Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G, který má pět vrcholů a splňuje k(G) = x'(G) ^ 0. Pokud takový graf neexistuje, zdůvodněte proč.
6. (10 bodů) Určete, pro která přirozená čísla x & y je posloupnost
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í obyčejné grafy G se šesti vrcholy splňující k'(G) > k(G).
8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí zdůvodněte.
2. (10 bodů) Určete chromatický polynom grafu
(1,1,1,1,1,1,x,x + 2,5,í/)
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ů) Necht n > 3 je celé číslo a G = (V, E) je obyčejný graf sestávající ze dvou kružnic v1}..., vn a w1}..., wn (v tomto pořadí) a dvou vrcholů v a w. Tyto vrcholy jsou navíc pro i = l,...,n spojeny hranami vw,Wí,wwí,VíWí. 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 větu o struktuře 2-souvislých grafů.
13. (10 bodů) Dokažte, že pro každé přirozené číslo n existuje přirozené číslo k takové, že každá posloupnost přirozených čísel délky k obsahuje několik po sobě jdoucích čísel, jejichž součet je dělitelný n.