Teorie grafů – podzim 2018 – 4. 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ů) Následující graf vyjadřuje pravděpodobnost, do které z místností A,
B, C, D se nehlídané dítě přesune během jedné minuty. Určete, do které místnosti
je třeba dítě umístit, chceme-li maximalizovat pravděpodobnost, že když se je po
čtyřech minutách vydáme hledat, najdeme je hned v první prohledávané místnosti.
(Jako první prohledáváme samozřejmě místnost, kde se dítě nachází s největší
pravděpodobností.)
A
1
2

1
4
//
1
4

B
3
4
oo
1
4

C
1
2
OO
1
2
// D
1
4
oo
1
4
__
1
2
OO
3. (5 bodů) Dejte příklad souvislého grafu G s devíti nebo deseti vrcholy takového,
že velikost nejmenšího vrcholového pokrytí G je o 2 vyšší než velikost největšího
párování na G. Pokud takový graf neexistuje, zdůvodněte proč.
4. (5 bodů) Dejte příklad souvislého grafu se šesti vrcholy, který má právě 16 koster.
Pokud takový graf neexistuje, zdůvodněte proč.
5. (5 bodů) Dejte příklad grafu G s devíti vrcholy, který má 25 hran a splňuje
κ(G) = 2 a κ (G) = 4. 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í obyčejné grafy G s pěti vrcholy
takové, že χ (G) = χ(G) a existují právě dva izomorfismy G na G.
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 ≥ 1 je přirozené číslo a G je obyčejný graf s vrcholy
u1, . . . , un+1, v1, . . . , vn, w1, . . . , wn+1
a hranami
uiuj, wiwj pro i, j ∈ {1, . . . , n + 1}, i = j,
uivj, wivj pro i ∈ {1, . . . , n + 1}, j ∈ {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 síť a tok v síti.
12. (5 bodů) Formulujte Ramseyho větu pro k barev.
13. (10 bodů) Dokažte, že každý 2-souvislý graf o n vrcholech, který není izomorfní
grafu Cn, má alespoň 3n − 4 koster.