Podpora výuky předmětu Diskrétní matematika
Sbírka příkladů
Lucia Macášková, Tadeáš Kučera,
Jan Kvapil, Vladimír Sedláček
27. ledna 2016
Obsah
1 Logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Zobrazení a mohutnost množin . . . . . . . . . . . . . . . . . . . 8
4 Relace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Uspořádané množiny . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6 Ekvivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7 Kombinatorika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8 Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2
Tato sbírka vznikla v rámci programu podpory výuky předmětu Diskrétní
matematika M1121.
Při vytváření sbírky bylo naší snahou pomoci studentům předmětu Diskrétní
matematika pochopit zaváděné pojmy a také souvislosti mezi jednotlivými tématy.
Proto se může stát, že některé příklady předpokládají znalosti napříč jednotlivými
kapitolami. Seznam příkladů, u kterých je tento fakt nejzásadnější,
uvádíme na konci toho úvodu (v seznamu číslo za dvojtečkou odkazuje na číslo
kapitoly).
Bylo-li to možné, snažili jsme se vyjadřovat co nejpřesněji a formálně správně,
ale kromě tradičních příkladů bylo naším cílem vymyslet i příklady motivační
nebo méně tradiční. V některých příkladech jsme si tak dovolili vyjádřovat se
neformálně. Oboje snad pomůže čtenáři vypracovat si intuici v daných oblastech
a přitom si zachovat schopnost vyjadřovat se formálně správně.
Na tomto místě bychom rádi poděkovali Mgr. Davidu Krumlovi, Ph.D. za
pomoc s vedením projektu a Veronice Kutálkové za přečtení sbírky a odhalení
mnoha nedostatků. Za veškeré zbývající chyby ovšem nesou zodpovědnost autoři
sami. Pokud nějaké nedostatky objevíte, sdělte je laskavě na adresu:
diskretniprojekt2015@gmail.com
Ke sbírce existuje také řešení. Oba dokumenty byly vysázeny pomocí balíku
LATEX, obrázky pomocí balíku TikZ.
Autoři
1. Logika
1.1: 4, 5, 6
1.2: 4, 5, 6
2. Množiny
2.2: 3
2.5: 3
3. Zobrazení a mohutnost množin
4. Relace
4.21: 5,6
5. Uspořádané množiny
5.9: 7
6. Ekvivalence
6.2: 7
7. Kombinatorika
8. Grafy
8.2: 5
8.3: 5
8.4: 5
3
1 LOGIKA
Zadání příkladů
1 Logika
Příklad 1.1. Ukažte, že ekvivalence formulí je skutečně relací ekvivalence. Dále
uvažme rozklad množiny formulí a symbolem [ϕ] označme třídu formulí, které
jsou ekvivalentní s formulí ϕ, tedy třídu tohoto rozkladu reprezentovanou prvkem
ϕ. Nyní definujme relaci → na tomto rozkladu vztahem [ϕ] → [ψ] , právě
když ϕ implikuje ψ. Ukažte, že → je relací uspořádání.
Příklad 1.2. Uveďte příklad výroků (resp. ekvivalentních tříd výroků), jejichž
Hasseovský diagram příslušný relaci → z předešlého příkladu má tento tvar:
A
DB C
FE
G
a)
A
C
E
D
B
b)
A
B
D
F
E
C
c)
Obr. 1: Hasseovy diagramy ekvivalentních tříd výroků.
Příklad 1.3. Nechť x je přirozené číslo. Mějme následující výroky:
a) A : x je sudé,
b) B : x je prvočíslo,
c) C : x je dělitelné 6,
d) D : x > 3,
e) E : x ≡ 6 (mod 12),
f) F : x = 5
g) G : x2
= −1,
h) H : x2
= 2x.
Pro každou dvojici těchto výroků rozhodněte, zda jeden implikuje druhý.
Příklad 1.4. V následující formuli jsou znakem • zaznačena místa pro kvantifikátory
(∃, ∀). Nalezněte všechny možnosti, jak tyto kvantifikátory doplnit tak,
aby byly tyto formule pravdivé.
• k ≥ 2, k ∈ N, • n ∈ N, • r ∈ N : kr
∈ [n, k · n]
4
1 LOGIKA
Příklad 1.5. Pro každé n ∈ N je dána formule ψn s proměnnými x1, . . . , x2n ∈ N
předpisem ψn = ∃x1∀x2 . . . ∃x2n−1∀x2n : V , kde V je výrok o proměnných
x1, . . . , x2n ∈ N. Rozhodněte, zda a případně pro která n platí formule ψn,
pokud
a) n = 2 a V = (x1x3 ≤ x2x4),
b) n = 2 a V = (x1x2 ≤ x3x4),
c) n = 2 a V = (x1x2 ≥ x3x4),
d) V = (x1x3 . . . x2n−1 ≤ x2x4 . . . x2n),
e) V = (x1x3 . . . x2n−1 ≥ x2x4 . . . x2n),
f) V = (x1x2 . . . xn ≤ xn+1 . . . x2n),
g) V = (x1x2 . . . xn ≥ xn+1 . . . x2n).
Příklad 1.6. Pro každé n ∈ N je dána formule ϕn s proměnnými x1, . . . , x2n ∈ N
předpisem ϕn = ∀x1∃x2 . . . ∀x2n−1∃x2n : V , kde V je výrok o proměnných
x1, . . . , x2n ∈ N. Rozhodněte, zda a případně pro která n platí formule ϕn,
pokud
a) n = 2 a V = (x1x3 ≤ x2x4),
b) n = 2 a V = (x1x2 ≤ x3x4),
c) n = 2 a V = (x1x2 ≥ x3x4),
d) V = (x1x3 . . . x2n−1 ≤ x2x4 . . . x2n),
e) V = (x1x3 . . . x2n−1 ≥ x2x4 . . . x2n),
f) V = (x1x2 . . . xn ≤ xn+1 . . . x2n),
g) V = (x1x2 . . . xn ≥ xn+1 . . . x2n).
Příklad 1.7. Nechť X, Y jsou výroky a v nějaká valuace. Čemu odpovídají
následující výrazy?
a) min{v(X), v(Y )},
b) max{v(X), v(Y )},
c) v(X) · v(Y ),
d) 1 − (1 − v(X)) · (1 − v(Y )),
e) v(X) + v(Y ) (mod 2).
Příklad 1.8. Pro každý podbod určete, kolik existuje binárních logických spojek
s příslušnou vlastností pro všechny výroky X, Y .
a) X Y ∼= ¬X ¬Y ,
b) ¬(X Y ) ∼= ¬X ¬Y ,
c) (X ¬X) Y ∼= Y .
Příklad 1.9. Udejte příklad binární logické spojky s vlastností
(X Y ) Z ∼= X (Y Z).
5
2 MNOŽINY
2 Množiny
Příklad 2.1. Nechť množina M ⊆ R má tu vlastnost, že každá její neprázdná
podmnožina má nejmenší i největší prvek. Ukažte, že M je konečná.
Příklad 2.2. Ukažte, že kartézský součin množin je „kategoriální součin“, tj.
pro všechny množiny A, B, C a zobrazení f : C → A, g: C → B existuje právě
jedno zobrazení h: C → A×B splňující pA◦h = f, pB◦h = g, kde pA : A×B → A
a pB : A × B → B jsou příslušné projekce dané předpisem pA((a, b)) = a a
pB((a, b)) = b.
C
A × B
A B
f g
h
pA pB
Obr. 2: Diagram kategoriálního součinu.
Příklad 2.3. Co je sjednocením prázdného systému množin?
Příklad 2.4. Je dána množina A. Buď U prázdný systém podmnožin množiny
A. Určete průnik U.
Příklad 2.5. Disjunktní sjednocení můžeme definovat například jako
A B = {(1, a) | a ∈ A} ∪ {(2, b) | b ∈ B}.
Ukažte, že disjunktní sjednocení množin je „kategoriální součet“, tj. pro všechny
množiny A, B, C a zobrazení f : A → C, g: B → C existuje právě jedno zobrazení
h: A B → C splňující h ◦ iA = f, h ◦ iB = g, kde iA : A → A B
a iB : B → A B jsou příslušná vnoření definovaná vztahy iA(a) = (1, a) a
iB(b) = (2, b).
C
A B
A B
f g
iA iB
h
Obr. 3: Diagram kategoriálního součtu.
Příklad 2.6. Nechť x, y, z ∈ N a A, B, C jsou množiny. Rozhodněte o pravdivosti
následujících tvrzení:
a) {∅} ∈ {x, y, ∅},
b) ∅ ⊆ {x, y, ∅},
c) {{∅}} ∈ {{∅}},
6
2 MNOŽINY
d) {∅} ⊆ {{∅}},
e) {z} ⊆ {x, y, {z}},
f) B ∈ P(A) ⇐⇒ B ⊆ A,
g) (A ∈ B) ∧ (B ∈ C) =⇒ A ∈ C,
h) A ∪ B = A ∪ C =⇒ B = C,
i) {x, y, ∅} \ ∅ = {x, y},
j) (A \ B) × C = (A × C) \ (B × C),
k) A × ∅ = ∅,
l) A × B = B × A,
m) A, B ⊆ C =⇒ A ∩ B = A ∪ B,
n) (A ÷ B) ÷ C = A ÷ (B ÷ C),
o) (A \ B) \ C = A \ (B \ C),
p) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),
q) A \ (B \ C) = (A \ B) ∪ C.
Příklad 2.7. Určete všechny množiny A, pro které platí
P(∅) ⊆ A ⊆ P({∅}) a {∅} ∈ A.
Příklad 2.8. Následující množiny zadané výčtem prvků popište formulí:
a) {2, 3, 5, 7, 11, 13, 17, . . . },
b) {1, 4, 16, 64, 256, . . . },
c) {0, 1, 3, 7, 15, 31, 63, . . . },
d) {1, 22, 333, 4444, . . . , 999999999},
e) {1, 22, 333, 4444, . . . }.
7
3 ZOBRAZENÍ A MOHUTNOST MNOŽIN
3 Zobrazení a mohutnost množin
Příklad 3.1. Nechť X, Y jsou neprázdné množiny. Rozhodněte, zda lze každé
zobrazení f : X → Y zapsat jako složení f = g ◦ h, kde
a) g je injektivní a h je surjektivní,
b) g je surjektivní a h je injektivní.
Příklad 3.2. Rozhodněte, které z diagramů definují zobrazení z množiny X do
množiny Y . Pro tyto funkce určete jejich vlastnosti.
X Y
a)
X Y
b)
X Y
c)
X Y
d)
Příklad 3.3. Nechť M je množina studentů. Rozhodněte, zda je v jednotlivých
bodech relace R ⊆ M × X zobrazením. Relace R je zadána následovně:
a) X je množina univerzit. Každý student je v relaci s univerzitou, na které
studuje.
b) X = N0 a každý student je v relaci se svým věkem.
c) X je množina lidí. Každý student je v relaci se svým partnerem či part-
nerkou.
Příklad 3.4. Nechť X, Y jsou libovolné neprázdné množiny, f : X → Y je
libovolné zobrazení a {Ai}i∈I je systém podmnožin množiny Y. Dokažte, že
a) f−1
( Ai) = f−1
(Ai),
b) f−1
( Ai) = f−1
(Ai).
Mohutnost množiny
Příklad 3.5. Označme P množinu všech konečných podmnožin množiny přirozených
čísel. Je dáno zobrazení f : P → N0, které zobrazí konečnou množinu
A na počet jejích prvků.
a) Popište Jf .
b) Popište P/Jf a rozhodněte, zda existuje nějaká bijekce g : P/Jf → N0.
Příklad 3.6. Určete mohutnost množiny všech vrcholů nekonečného binárního
stromu (binárním stromem rozumíme množinu neprázdných konečných posloupností
symbolů 0 a 1).
8
3 ZOBRAZENÍ A MOHUTNOST MNOŽIN
Příklad 3.7. Nechť a, b, c, d jsou reálná čísla splňující a < b, c < d. Ukažte, že
libovolné dva otevřené intervaly (a, b), (c, d) mají stejnou mohutnost.
Příklad 3.8. Nechť a, b jsou reálná čísla splňující a < b. Ukažte, že otevřený
interval (a, b) má stejnou mohutnost jako množina všech reálných čísel.
Příklad 3.9. Nechť A, B jsou množiny s vlastností, že A ÷ B je spočetná
množina. Určete, jakou kardinalitu (konečná / spočetná / nespočetná) může
mít množina A víte-li, že množina B je
a) konečná,
b) spočetná,
c) nespočetná.
9
4 RELACE
4 Relace
Příklad 4.1. Určete počet všech relací na konečné množině A.
Příklad 4.2. Pro relaci R na množině A označme R1
= R, Rn
= R ◦ Rn−1
.
a) Ukažte, že je-li množina A konečná, pak pro libovolnou relaci R na množině
A existují m, n ∈ N, m < n taková, že Rm
= Rn
. Dále ukažte, že pro
nekonečnou množinu A toto platit nemusí.
b) Najděte takovou konečnou množinu A a na ní relaci R tak, že Rn
= Rn+1
pro všechna n ∈ N.
Příklad 4.3. Pro relaci R na množině A označme R−1
inverzní relaci k R a
∆A = {(a, a) | a ∈ A} diagonální relaci. Ukažte, že platí následující tvrzení:
a) R je reflexivní, právě když ∆A ⊆ R.
b) R je symetrická, právě když R = R−1
.
c) R je antisymetrická, právě když R ∩ R−1
⊆ ∆A.
d) R je tranzitivní, právě když R2
⊆ R.
e) R je reflexivní a antisymetrická, právě když R ∩ R−1
= ∆A.
Příklad 4.4. Nechť R je acyklická relace na A, tj. neexistuje konečná posloupnost
prvků a1, a2, . . . , an ∈ A splňujících a1Ra2, a2Ra3, . . . , anRa1. Dokažte, že
pak na A existuje relace uspořádání, která obsahuje R.
Příklad 4.5. Na množině A všech lidí uvažujeme relace R, S určené tak, že
a) aRb, právě když a je rodičem b,
b) aSb, právě když a je sourozencem b.
Slovně popište význam relací R−1
, S−1
, R ◦ S, S ◦ R, R2
, S2
. Relaci S přitom
nepovažujeme za reflexivní.
Příklad 4.6. Na množině R uvažujeme relaci R určenou vztahem (x, y) ∈ R,
právě když
a) x + y = 0,
b) |x| = |y|,
c) x > y,
d) x ≥ y,
e) x − y je racionální,
f) xy ≥ 0,
g) x je iracionální násobek y,
h) je tato sbírka přínosná.
10
4 RELACE
Určete vlasnosti (reflexivitu, symetrii, antisymetrii, tranzitivitu) jednotlivých
relací.
Příklad 4.7. Nechť T je množina všech trojúhelníků v rovině. Relace P a S na
množině T jsou určeny tím, že t1Pt2, pokud jsou t1, t2 podobné a t1St2, pokud
jsou t1, t2 shodné. Jaké mají tyto dvě relace vlastnosti (reflexivitu, symetrii,
antisymetrii, tranzitivitu)?
Příklad 4.8. Je dána relace R na množině všech států světa, do níž patří
všechny dvojice států, které mají společnou část svých hranic. Je tato relace
reflexivní? Je symetrická? A je tranzitivní? Popište její druhou mocninu, tj.
složení jí se sebou samou.
Příklad 4.9. Každému dennímu času přiřadíme dvojici reálných čísel (α, β),
α, β ∈ [0, 2π) takovým způsobem, že úhel mezi spojnicí středu hodin s dvanáctkou
a malou ručičkou je α a úhel mezi spojnicí středu hodin s dvanáctkou a
velkou ručičkou je β (viz obrázek). Uvažme relaci ρ na množině [0, 2π) která
obsahuje právě ty dvojice (α, β), pro něž existuje denní čas, v němž úhel mezi
spojnicí středu hodin s dvanáctkou a malou ručičkou je α a úhel mezi spojnicí
středu hodin s dvanáctkou a velkou ručičkou je β. Je ρ zobrazení? Určete relaci
ρ−1
. Je ρ−1
zobrazením?
12
3
6
9
α
β
Obr. 4: Hodiny s vyznačenými úhly α, β.
Příklad 4.10. Uvažme relaci ρ na množině R2
. Rozhodněte, zda je ρ reflexivní,
symetrická, tranzitivní, antisymetrická, pokud
a) ρ = {((a, b), (c, d)); |ad − bc| = 1},
b) ρ = {((a, b), (c, d)); |ad − bc| = 0}.
Příklad 4.11. Relace ρ je dána na množině všech lidí vztahem (A, B) ∈ ρ,
právě když je osoba B o rok starší než osoba A. Rozhodněte, zda je ρ reflexivní,
symetrická, tranzitivní, antisymetrická.
Příklad 4.12. Relace ρ je dána na množině všech lidí vztahem (A, B) ∈ ρ, právě
když osoba B obdivuje osobu A. Rozhodněte, zda je ρ reflexivní, symetrická,
tranzitivní, antisymetrická.
Příklad 4.13. Mějmě plně obsazený kulatý stůl s n místy. Relace ρ je dána na
množině všech lidí sedících u tohoto stolu vztahem (A, B) ∈ ρ, právě když osoba
B sedí vedle osoby A. Rozhodněte, zda je ρ reflexivní, symetrická, tranzitivní,
antisymetrická.
11
4 RELACE
Příklad 4.14. Ve třídě hráli studenti páku (každý s každým právě jednou,
kromě sebe sama). Řekneme, že student A je v relaci R se studentem B, pokud
se A utkal s B, a student A je v relaci S se studentem B, pokud A vyhrál nad
B. Rozhodněte, zda jsou relace R, S reflexivní, symetrické, tranzitivní, antisy-
metrické.
Příklad 4.15. Nechť A = {a, b, c, d}. Udejte příklad relace V ⊆ A2
tak, že
a) V 3
= V a V = ∅,
b) V 3
= V a V 2
= V ,
c) V 4
= V 2
a V 3
= V.
Příklad 4.16. Nechť A = {a, b, c}. Udejte příklad relace V ⊆ A2
tak, že
a) V 2
= ∅ a V = ∅,
b) V 3
= ∅ a V 2
= ∅.
Příklad 4.17. Buď A = {a, b}. Udejte příklad relací U, V, W ⊆ A2
tak, že
U ◦ V = U ◦ W a V = W.
Příklad 4.18. Buď A libovolná množina. Nechť jsou dány reflexivní relace
U, V ⊆ A2
. Rozhodněte, zda obecně platí následující inkluze:
a) U ◦ V ⊆ V ,
b) U ◦ V ⊇ V .
Příklad 4.19. Nechť n je přirozené číslo. Uveďte příklad množiny A a na ní
relace R tak, že pro všechna přirozená k, l platí Rk
= Rl
, pokud k < l < n, a
Rk
= Rl
, pokud n − 1 ≤ k < l.
Příklad 4.20. Následující obrázek zadává relaci na množině {a, b, c, d}.
a b c d
a) Rozhodněte, zda je tato relace reflexivní, symetrická, antisymetrická a
tranzitivní.
b) Pokud se nejedná o ekvivalenci, přikreslete co možná nejméně šipek, aby
to ekvivalence byla.
c) Pokud se nejedná o uspořádání, smažte co možná nejméně šipek, aby to
uspořádání bylo.
Příklad 4.21. Nalezněte všechny relace na množině přirozených čísel, které
jsou zároveň ekvivalencemi i uspořádáními.
12
5 USPOŘÁDANÉ MNOŽINY
5 Uspořádané množiny
Příklad 5.1. Uvažujme uspořádanou množinu (N, |). Rozhodněte, zda
a) každá podmnožina N má supremum,
b) každá konečná podmnožina N má supremum,
c) každá neprázdná podmnožina N má infimum,
d) se jedná o svaz.
Příklad 5.2. Uvažme Hasseovský diagram množiny přirozených čísel uspořádané
dělitelností. Určete počet hran vedoucí „zespodu“ do čísla k. Jinými slovy,
určete, kolik má číslo k předchůdců v uspořádání přirozených čísel podle děli-
telnosti.
Příklad 5.3. Rozhodněte, zda existuje
a) dvojice vzájemně neizomorfních lineárních uspořádání množiny N,
b) nekonečně mnoho vzájemně neizomorfních lineárních uspořádání množiny
N,
c) nespočetně mnoho vzájemně neizomorfních lineárních uspořádání množiny
N.
Příklad 5.4. Nechť A, je uspořádaná množina, jejíž každá podmnožina má
supremum. Dokažte, že pak má každá její podmnožina také infimum.
Příklad 5.5. Injektivní zobrazení f : (A, ) → (B, ) mezi uspořádanými množinami
s vlastností a b ⇐⇒ f(a) f(b) pro všechna a, b ∈ A nazýváme
vnoření.
a) Ukažte, že každou uspořádanou množinu (X, ) lze vnořit do (2X
, ⊆).
b) Ukažte, že každou konečnou uspořádanou množinu lze vnořit do (N, |).
c) Ukažte, že každou nejvýše spočetnou lineárně uspořádanou množinu lze
vnořit do (Q, ≤).
Příklad 5.6. Označme Eq(X) množinu všech ekvivalencí na množině X uspořádanou
inkluzí.
a) Nakreslete Hasseův diagram pro Eq({1, 2, 3}).
b) Dokažte, že Eq(X) je svaz.
Příklad 5.7. Zjistěte, zda existuje, a pokud ano, jaký nejmenší počet prvků
může mít uspořádaná množina M s danými vlastnostmi (pro každý bod zvlášť).
Pokud existuje, uveďte ji. Pokud neexistuje, sepište důkaz.
a) M obsahuje dva maximální a dva minimální prvky.
b) M obsahuje suprema všech svých podmnožin, ale existuje podmnožina,
která nemá infimum.
c) M obsahuje dva největší prvky.
13
5 USPOŘÁDANÉ MNOŽINY
d) M obsahuje jeden minimální, ale žádný nejmenší prvek.
Příklad 5.8. Nalezněte všechny šestiprvkové úplné svazy (až na izomorfizmus).
Příklad 5.9. Kolik existuje izotonních zobrazení z m-prvkového do n-prvkového
řetězce?
Příklad 5.10. Dokažte, že úplný svaz všech podmnožin dvouprvkové množiny
není izomorfní s čtyřprvkovým řetězcem.
Příklad 5.11. Nechť I = [0, 1] a uvažme uspořádanou množinu (I, ≤). Rozhodněte,
zda je množina všech
a) zobrazení I → I
b) spojitých funkcí I → I
c) diferencovatelných funkcí I → I
d) rostoucích funkcí I → I
e) neklesajících funkcí I → I
úplný svaz.
Příklad 5.12. Uvažme množinu prvních deseti římských čísel {I, . . . , X} = R a
na ní relaci ≤, kde x ≤ y, právě když y lze vytvořit z x přiložením nezáporného
počtu sirek (např. I se skládá z jedné sirky a V i X ze dvou sirek, číslo V
nelze přidáním sirky získat z I). Ukažte, že ≤ je relace uspořádání a nakreslete
příslušný Hasseův diagram.
Příklad 5.13. Rozhodněte a zdůvodněte, zda mezi danými dvěma uspořádanými
množinami A, B existuje zobrazení f : A → B, které je izotonní, popřípadě
izomorfní. V případě, že izomorfizmus neexistuje, upravte zadaná uspořádání
tak, aby izomorfizmus existoval.
a) A = (Z \ N, ≤) a B = (Z, ≤).
b) A = (N, ) a B = (Z \ {0}, ),
kde a b, právě když (2|(a − b) ∧ a ≤ b) ∨ (2|a ∧ 2 b) a a b, právě když
(a, b ≥ 0 ∧ a ≤ b) ∨ (a, b ≤ 0 ∧ a ≥ b) ∨ (a ≤ 0 ∧ b > 0).
0
−1
−2
...
(Z \ N, ≤)
1
...
0
−1
...
(Z, ≤)
5
...
3
1
...
4
2
(N, )
1
2
3
...
−3
−2
−1
(Z \ {0}, )
14
6 EKVIVALENCE
6 Ekvivalence
Příklad 6.1. Pro daná zobrazení f popište rozklad Dom(f)/Jf :
a) f : {x | x je člověk} → {x | x je den v přestupném roce},
f(x) = den v roce, ve kterém se x narodil,
b) f : {kruh, trojúhelník, čtverec, obdélník} → N0,
f(x) = počet vrcholů úvaru x,
c) f : R → R, f(x) = |x|,
d) f : Z → Z, f(x) = x (mod 7),
e) f : Z × (Z \ {0}) → Q, f(x, y) = x
y ,
f) f : R × R → R, f(x, y) = x2
+ y2
,
g) f : R×R → R, f(x, y) = x , kde x značí největší celé číslo nepřesahující
x, např. −1, 156 = −2, π = 3.
Příklad 6.2. Určete počet všech rýmových schémat čtyřřádkové básně. Pokuste
se výsledek zobecnit pro víceřádkové básně.
Příklad 6.3. Uvažme množinu římských čísel {I, . . . , X} = R, a na ní relaci
ρ „skládat se ze stejného počtu sirek“ (např. I se skládá z jedné sirky a V i
X ze dvou sirek). Ukažte, že ρ je relací ekvivalence a popište příslušný rozklad
množiny R.
Příklad 6.4. Najděte zobrazení, jehož jádrem je následující ekvivalence:
a) relace „chodit do stejné třídy“ na množině všech žáků dané školy,
b) relace „mít stejný počet nohou“ na množině všech zvířat.
Příklad 6.5. Připomeňme, že pro vektorové prostory U, V a lineární zobrazení
ϕ: U → V značíme ker ϕ = {u ∈ U | ϕ(u) = 0} jádro zobrazení ϕ (ve smyslu
lineární algebry). Definujme na U relaci ∼ vztahem u ∼ v, právě když u −
−v ∈ ker ϕ. Ukažte, že ∼ je ekvivalence a nalezněte jádro zobrazení ϕ (ve smyslu
teorie množin) definované vztahem Jϕ = {(u, v) ∈ U × U | ϕ(u) = ϕ(v)}.
15
7 KOMBINATORIKA
7 Kombinatorika
Příklad 7.1. Dědeček koupil pozemek tvaru obdélníka o šířce 24 a délce 42
metrů, který chce nechat náhodně osázet 80 stromy. Jeho vnuk Karlík dostal
novou houpací síť, ale má strach, že nenajde dva stromy, jejichž vzdálenost není
více než 5 metrů. Ukažte, že existují dva stromy se vzdáleností nejvýše 5 metrů.
Příklad 7.2. Obdélník o stranách m, n ∈ N byl čtvercovou sítí rozdělen na mn
jednotkových čtverců.
a) Kolik vzniklo obdélníků?
b) Kolik vzniklo čtverců? (Výsledek stačí uvést v podobě sumy.)
Příklad 7.3. Kolika způsoby lze na šachovnici (o rozměrech 8 × 8 čtverců)
umístit dva koně, aby se vzájemně ohrožovali?
Příklad 7.4. Kolika způsoby si může sednout 7 lidí do kruhu ze 7 stoliček,
pokud
a) jsou stoličky identické,
b) je každá stolička jiné barvy.
Příklad 7.5. Pět řečníků A, B, C, D, E má vystoupit na konferenci, určete počet
možných pořadí jejich výstupů, pokud
a) má A vystoupit po B,
b) má A vystoupit hned po B.
Příklad 7.6. Rozhodněte a zdůvodněte, zda musí mít alespoň dva obyvatelé
vesnice s právě 500 obyvateli stejné iniciály. Jméno i příjmení začíná jedním z
26 písmen anglické abecedy.
Příklad 7.7. Určete, kolika nulami končí číslo 258!
Příklad 7.8. Je dáno deset bodů v rovině, z nichž žádné tři neleží na jedné
přímce.
a) Kolik různých úseček můžeme vytvořit spojováním těchto bodů?
b) Kolik různých trojúhelníků tvoří úsečky z předcházející podúlohy? (Jako
možné vrcholy pro tyto trojúhelníky uvažujeme pouze výchozí body.)
c) Označme A jeden z deseti výchozích bod. Kolik z předešlých trojúhelníků
má A za jeden ze svých vrcholů?
Příklad 7.9. Dokažte, že součin libovolných k po sobě jdoucích přirozených
čísel je dělitelný k!.
Příklad 7.10. Dokažte, že pro všechna přirozená čísla n, k, l taková, že k+l ≤ n,
platí
n
k
·
n − k
l
=
n
l
·
n − l
k
.
Příklad 7.11. Dokažte, že pro každé přirozené n, n ≥ 2, platí
2n
2
= 2 ·
n
2
+ n2
.
16
7 KOMBINATORIKA
Princip inkluze a exkluze
Příklad 7.12. Na škole se 54 žáků angažuje v 11 zájmových kroužcích. Každý
kroužek má aspoň 15 členů a nikdo nechodí do více než tří kroužků. Každé
tři kroužky mají alespoň jednoho společného člena. Dokažte, že existují dva
kroužky, které mají alespoň 6 společných členů.
Příklad 7.13. Nechť n ∈ N. Kolika způsoby můžeme posadit v kině n manželských
párů do řady s 2n místy tak, aby žádný manželský pár neseděl pospolu?
Příklad 7.14. Alenka dostane každý den od maminky korunu. Někdy si za ni
koupí nanuk, jindy si ji schová. Tatínek ji nabádá, aby si polovinu peněz šetřila
na něco pořádného. Občas dokonce nahlédne do pokladničky, a není-li tam
alespoň polovina korun, řeční. Kolika způsoby si může Alenka během prvních
30 dnů kupovat nanuky, aby jich snědla co nejvíc a přitom měla od otce klid?
Maminka ji více než jeden nanuk denně nepovolí.
17
8 GRAFY
8 Grafy
Příklad 8.1. Nechť V, W jsou množiny vrcholů a E, F jim odpovídající množiny
hran. Zobrazení f : (V, E) → (W, F) mezi grafy se nazývá homomorfismus,
pokud pro všechna u, v ∈ V platí
(u, v) ∈ E =⇒ (f(u), f(v)) ∈ F.
Nechť k ∈ N. Ukažte, že graf je (vrcholově) k-obarvitelný, právě když z něj vede
homomorfismus do úplného grafu na k vrcholech.
Příklad 8.2. Uvažme Hasseův diagram množiny všech podmnožin n-prvkové
množiny uspořádané inkluzí, který budeme chápat jako neorientovaný graf G.
Pro každé n ∈ N řešte následující úlohy:
a) Rozhodněte, zda je G eulerovský.
b) Určete, kolika nejméně barvami je G vrcholově obarvitelný.
(Nápověda. Uvědomme si, že graf G odpovídá n-rozměrné krychli.)
Příklad 8.3. Uvažme Hasseův diagram množiny čísel {1, 2, . . . , 12} uspořádaných
dělitelností, který budeme chápat jako neorientovaný graf G. Řešte následující
úlohy:
a) Rozhodněte, zda je G eulerovský.
b) Rozhodněte, zda je G rovinný.
c) Nyní ohodnoťme hrany grafu G následovně. Nechť a, b jsou vrcholy grafu
G. Pokud a | b a a je spojené hranou s b, potom přiřaďme této hraně číslo
b
a . Nalezněte nějakou minimální kostru grafu G.
Příklad 8.4. Uvažme Hasseův diagram množiny digitálních číslic 0, 1, . . . 9 s
uspořádáním ≤, kde a ≤ b, právě když digitální obraz a je podmnožinou digitálního
obrazu b (viz obrázek), který budeme chápat jako neorientovaný graf G.
Řešte následující úlohy:
a) Rozhodněte, zda G je eulerovský.
b) Rozhodněte, zda G je rovinný.
c) Nyní ohodnoťme hrany grafu G následovně: pokud a ≤ b a a je spojené
hranou s b, potom přiřaďme této hraně číslo |a − b|. Nalezněte nějakou
minimální kostru grafu G.
Obr. 5: Příklad uspořádání digitálních číslic, např. 4 ≤ 8.
18
8 GRAFY
Příklad 8.5. Najděte všechny vzájemně neizomorfní grafy, které mají právě 6
vrcholů, právě 7 hran a obsahují právě 2 kružnice.
Příklad 8.6. Uveďte příklad nezáporně ohodnoceného souvislého grafu s šesti
vrcholy, z nichž dva vrcholy u, v splňují, ž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.
Příklad 8.7. Uveďte příklad ohodnoceného souvislého grafu s pěti vrcholy,
který obsahuje právě jednu záporně ohodnocenou hranu a dva jeho vrcholy u, v
splňují, že při výpočtu nejkratších cest z u dává Dijkstrův algoritmus správný
výsledek, ale při výpočtu nejkratších cest z v ne.
Příklad 8.8. Najděte všechny vzájemně neizomorfní grafy se čtyřmi vrcholy.
Příklad 8.9. Najděte všechny vzájemně neizomorfní eulerovské grafy s pěti
vrcholy.
Příklad 8.10. Najděte minimální kostru následujícího ohodnoceného grafu.
Kolik různých minimálních koster tento graf má?
2
3
2
3
3
3 1
1
1
2
Příklad 8.11. Kolik koster, až na izomorfismus, mají následující grafy?
a) b)
19
8 GRAFY
Příklad 8.12. Pomocí Dijkstrova algoritmu určete nejkratší cesty z vrcholu u
do všech ostatních vrcholů v následujícím grafu.
uu1 u2
u3 u4 u5
4
1
3
3
1
6
5 1
2
3
1
Příklad 8.13. Rozhodněte, zda jsou následující grafy izomorfní. Pokud ano,
najděte (nějaký) izomorfismus. Jako pomůcku uvedeme jedno tvrzení bez důkazu.
Nejdříve musíme ovšem definovat pojem indukovaného podgrafu grafu G.
Nechť G = (V, E) je graf. Graf H = (W, F) nazveme indukovaným podgrafem
grafu G, pokud H je podgraf grafu G a pro všechny vrcholy u, v ∈ H platí
(u, v) ∈ F ⇐⇒ (u, v) ∈ E.
Lemma. Grafy G1, G2 jsou izomorfní právě tehdy, když pro každou podmnožinu
H množiny nezáporných celých čísel jsou izomorfní podgrafy P1, P2 grafů
G1, G2, přičemž P1, P2 jsou indukované množinami všech vrcholů příslušných
grafů, jejichž stupeň leží v H.
Poznámka. Všimněte si, že ekvivalence z tvrzení je zajímavá pouze v jednom
směru – implikace zprava doleva platí triviálně volbou H = N0.
1)
a) b)
20
8 GRAFY
2)
a) b)
3)
a) b)
4)
a) b)
5)
a) b)
21
8 GRAFY
6)
a) b)
22