Teorie grafů – podzim 2024 – 1. termín
1. (10 bodů) Nalezněte největší párování v následujícím bipartitním grafu a svoje
tvrzení zdůvodněte.
• • • • • • • •
• • • • • • • •
2. (10 bodů) Když se v naší škole porouchá kotel, je vždy následující den provedena
oprava, přičemž s pravděpodobností 1/2 se kotel porouchá v den následující
po opravě znovu a pokud ne, tak se poté porouchá každý další den se stejnou
pravděpodobností 1/4. V první den školního roku proběhla oprava kotle. Určete,
s jakou pravděpodobností bude provedena oprava kotle devátý den školního roku.
(Výsledný výraz obsahující několik součinů víceciferných čísel vyhodnocovat ne-
musíte.)
3. (5 bodů) Dejte příklad 3-regulárního obyčejného grafu G s nejvýše deseti vrcholy,
který splňuje κ(G) = 2. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad hamiltonovského a eulerovského obyčejného grafu se šesti
vrcholy a jeho regulárního 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 souvislého bipartitního grafu s osmi vrcholy, který není
rovinný, ale odebráním kterékoli hrany z něj vznikne rovinný graf. 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, x, 5, 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é mají právě 64 koster a přitom neobsahují kružnici délky větší než 4 ani
podgraf izomorfní grafu K2,3.
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 ≥ 2 je celé číslo a G je obyčejný graf s 3n − 3 vrcholy sestávající
ze tří podgrafů izomorfních grafu Kn, přičemž každé dva z těchto podgrafů
mají společný právě jeden vrchol. Určete hranovou a vrcholovou souvislost G, jeho
hranové a vrcholové chromatické číslo, zda je G eulerovský a zda je hamiltonovský.
11. (5 bodů) Definujte tok v síti a jeho velikost.
12. (5 bodů) Formulujte vzorec pro výpočet největší velikosti párování a podmínku
charakterizující existenci perfektního párování v obyčejném grafu.
13. (10 bodů) Dokažte, že pro každé přirozené číslo n existuje přirozené číslo k takové,
že každá posloupnost k transformací množiny {1, . . . , n} obsahuje několik po
sobě jdoucích transformací, jejichž kompozice f (v pořadí určeném posloupností)
splňuje f(f(1)) = f(1).