Teorie grafů – podzim 2022 – 2. termín
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 uzavřených sledů délky 8 v grafu
A B
C D
3. (5 bodů) Dejte příklad netriviálního regulárního bipartitního rovinného eulerovského
grafu, který není 2-souvislý. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad ohodnoceného orientovaného grafu G, který neobsahuje
orientovanou kružnici záporné váhy, a jeho vrcholu v takového, že Dijkstrův algoritmus
správně určí nejmenší váhu cesty z v právě pro polovinu vrcholů grafu G.
Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad obyčejného grafu G se šesti vrcholy, který splňuje rovnosti
χ(G) = χ (G) = κ (G) = 3. 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, 2, 4, 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é obyčejné
grafy, které mají právě šestnáct koster.
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 je kladné celé číslo a nechť G je obyčejný graf s 5n vrcholy si,
ti, ui, vi a wi, pro i = 1, . . . , n, přičemž pro všechna i ∈ {1, . . . , n} indukují vrcholy
ti, ui, vi a wi v G úplný podgraf K4 a dále má G právě hrany siti, siui, visi+1 a
wisi+1, kde sn+1 značí vrchol s1. Určete hranovou a vrcholovou souvislost G, jeho
hranové a vrcholové chromatické číslo a zda je G eulerovský či hamiltonovský.
11. (5 bodů) Definujte síť a tok v síti.
12. (5 bodů) Formulujte Eulerův vztah pro graf s k komponentami.
13. (10 bodů) Dokažte, že každý 3-regulární graf, který lze (až na permutaci barev)
právě jedním způsobem řádně hranově obarvit třemi barvami, je hamiltonovský.