Podpora výuky předmětu Diskrétní matematika
Řešení sbírky příkladů
Lucia Macášková, Tadeáš Kučera,
Jan Kvapil, Vladimír Sedláček
27. ledna 2016
1
Obsah
1 Logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Zobrazení a mohutnost množin . . . . . . . . . . . . . . . . . . . 8
4 Relace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Uspořádané množiny . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Ekvivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7 Kombinatorika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8 Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2
1 LOGIKA
Řešení příkladů
1 Logika
Řešení 1.1. V první části si stačí uvědomit, že dvě formule jsou ekvivalentní,
jestliže mají stejnou tabulku pravdivostních hodnot, což je relace, která je reflexivní,
symetrická a tranzitivní. Díky tomu je následná definice relace → korektní.
Relace → je navíc reflexivní a tranzitivní, protože tuto vlastnost má i
„obyčejná“ implikace. Antisymetrie plyne z toho, že pokud se dva výroky navzájem
implikují, pak jsou ekvivalentní, tudíž leží ve stejné třídě rozkladu (což
je přesně důvod, proč jsme tento rozklad vůbec vytvořili – „obyčejná“ implikace
totiž antisymetrická není).
Řešení 1.2.
a) A : Vrah byl malý, kulhající muž a vražednou zbraní byla opotřebovaná,
železná motyka. B : Vrah byl malý muž. D : Vrah kulhal. C : Vražednou
zbraní byla opotřebovaná, železná motyka. E : Motyka byla opotřebovaná.
F : Motyka byla železná. G : Motyka byla železná nebo opotřebovaná.
b) A : x = 2, B : x = 3, C : x | 12, D : x | 18, E : x | 36.
c) A : Je to zelené jablko. B : Je to jablko. D : Roste to na stromě. C : Je to
zelené. E : Není to modré. F : Roste to na stromě nebo to není modré.
Řešení 1.3. K zápisu řešení jsme využili Hasseova diagramu, tedy např. výrok
G implikuje i výrok C, přestože tato skutečnost není naznačena samostatnou
šipkou.
H G
E B
DC
F
A
Řešení 1.4. Platí tyto čtyři ze všech osmi možných:
• ∀k ≥ 2 ∀n ∃r : kr
∈ [n, k · n]
• ∀k ≥ 2 ∃n ∃r : kr
∈ [n, k · n]
• ∃k ≥ 2 ∀n ∃r : kr
∈ [n, k · n]
• ∃k ≥ 2 ∃n ∃r : kr
∈ [n, k · n]
3
1 LOGIKA
Řešení 1.5.
a) ψ2 platí, stačí volit x1 = x3 = 1, pak 1 · 1 ≤ x2x4 pro všechna x2, x4 ∈ N.
b) ψ2 platí, stačí volit x1 libovolně a položit x3 = x1x2, pak x1x2 ≤ x1x2x4
pro všechna x4 ∈ N.
c) ψ2 neplatí, stačí na konci zvolit x4 ∈ N splňující x4 > x1x2
x3
(takové x4
zřejmě vždy existuje).
d) ψn platí pro každé n ∈ N, stačí volit x1 = x3 = · · · = x2n−1 = 1, pak
1 · 1 · . . . · 1 ≤ x2x4 . . . x2n pro všechna x2, x4, . . . , x2n ∈ N.
e) ψn neplatí pro žádné n ∈ N, stačí na konci zvolit x2n ∈ N splňující x2n >
> x1x2···xn
x3x4···x2n−1
(takové x2n zřejmě vždy existuje).
f) ψn platí pro každé n ∈ N, stačí volit x1, x3, . . . , x2n−3 libovolně a položit
x2n−1 = x1x2 · · · xn, pak
x1x2 · · · xn ≤ xn+1xn+2 · · · x2n−2x1x2 · · · xnx2n
pro všechna x2, x4, . . . , x2n ∈ N.
g) ψn neplatí pro žádné n ∈ N, stačí na konci zvolit x2n ∈ N splňující x2n >
> x1x2···xn
x3x4···x2n−1
(takové x2n zřejmě vždy existuje).
Řešení 1.6.
a) ϕ2 platí, stačí na konci zvolit x4 ∈ N splňující x4 ≥ x1x3
x2
(takové x4 zřejmě
vždy existuje).
b) ϕ2 platí, stačí na konci zvolit x4 ∈ N splňující x4 ≥ x1x2
x3
(takové x4 zřejmě
vždy existuje).
c) ϕ2 neplatí, je-li totiž zvoleno x3 ∈ N tak, že x1x2 < x3 (což se vždy může
stát), již nelze zvolit x4 ∈ N tak, aby x1x2 ≥ x3x4.
d) ϕn platí pro každé n ∈ N, stačí na konci zvolit x2n ∈ N splňující x2n ≥
≥ x1x3...x2n−1
x2x4...x2n−2
(takové x2n zřejmě vždy existuje).
e) ϕn platí pro každé n ∈ N, stačí zvolit x2 = x4 = · · · = x2n = 1, pak
x1x3 . . . x2n−1 ≥ 1 · 1 · . . . · 1 pro všechna x1, x3, . . . , x2n−1 ∈ N.
f) ϕn platí pro každé n ∈ N, stačí na konci zvolit x2n ∈ N splňující x2n ≥
≥ x1x2...xn
xn+1xn+2...x2n−1
(takové x2n zřejmě vždy existuje).
g) ϕn neplatí, pro žádné n ∈ N je-li totiž zvoleno x2n−1 ∈ N tak, že
x1x2 . . . xn
xn+1xn+2 . . . x2n−2
< x2n−1
(což se vždy může stát), již nelze zvolit x2n ∈ N tak, aby x1x2 . . . xn ≥
≥ xn+1xn+2 . . . x2n.
4
1 LOGIKA
Řešení 1.7. Řešení se nejsnáze ověří pomocí tabulek pravdivostních hodnot.
a) v(X ∨ Y ),
b) v(X ∧ Y ),
c) v(X ∧ Y ),
d) v(X ∨ Y ),
e) v(X XOR Y ) (XOR je tzv. výlučné „nebo“).
Řešení 1.8.
a) Hledaná spojka je jednoznačně určena hodnotami valuací v, w, kde v(X) =
= v(Y ) = 0, w(X) = 0, w(Y ) = 1, přičemž tyto volby jsou na sobě nezávislé
(hodnoty ostatních valuací jsou totiž určeny symetrií vůči transformaci
(X, Y ) → (¬X, ¬Y )). Proto je možných hledaných spojek celkem
22
= 4.
b) Hledaná spojka je jednoznačně určena hodnotami valuací v, w, kde v(X) =
= v(Y ) = 0, w(X) = 0, w(Y ) = 1, přičemž tyto volby jsou na sobě nezávislé
(hodnoty ostatních valuací totiž plynou z antisymetrie vůči transformaci
(X, Y ) → (¬X, ¬Y )). Proto je možných hledaných spojek celkem
22
= 4.
c) Zadaná ekvivalence musí platit pro všechny valuace v, w. Nejprve předpokládejme
v(X) = 1, v(Y ) = 0. Platí-li v(X Y ) = 1, pak v(X ¬X) = 1
a tedy v((X ¬X) Y ) = 1, ale přitom v(Y ) = 0. Proto musí platit
v(X Y ) = 0. Díky tomu pro w(X) = 0, w(Y ) = 0 dostáváme
w(X ¬X) = 0 a tedy w((X ¬X) Y ) = 1, což odpovídá rovnosti
w(Y ) = 1. Protože už víme, že výraz X ¬X může při vhodné valuaci
nabýt libovolné z hodnot 0, 1, musíme nyní položit u(X Y ) = u(Y )
pro všechny valuace u, což je v souladu s dosavadními volbami. Hledaná
spojka tedy existuje jediná. (Všimněme si, že se vlastně jedná o „projekci“
na druhý argument.)
Řešení 1.9. Příkladem hledané spojky je třeba spojka (X, Y ) ∼= ¬(X → Y ).
Například pro valuaci v, která splňuje v(X) = 1, v(Y ) = 0, v(Z) = 1 platí
v((X Y ) Z) = 0, ale v(X (Y Z)) = 1.
5
2 MNOŽINY
2 Množiny
Řešení 2.1. Pro spor předpokládejme, že M je nekonečná. Uvažujme posloupnost
{mi}∞
i=0 prvků množiny M tak, že m0 je nejmenší prvek množiny M, m1
je nejmenší prvek množiny M \ {m}, obecně pro každé i ∈ N0
mi = min {M \ {mj, j < i}} .
Protože je M nekonečná, tak pro žádné j ∈ N0 nebude množina M \{mj, j < i}
prázdná. Posloupnost jsme tedy definovali korektně, protože každá neprázdná
podmnožina M má nejmenší prvek. Je zřejmé, že {mi}∞
i=0 je rostoucí posloupnost.
Množina všech jejích prvků je podmnožina M, která však nemá největší
prvek. To je spor s předpokladem.
Řešení 2.2. Pokud nějaké zobrazení h : C → A × B splňuje pA ◦ h = f a
pB ◦h = g, pak pro všechna c ∈ C musí platit pA(h(c)) = f(c) a pB(h(c)) = g(c),
tedy h(c) = (f(c), g(c)). Na druhou stranu takto definované zobrazení h obě
podmínky splňuje, takže je jednoznačně určené.
C
A × B
A B
f g
h
pA pB
Obr. 1: Diagram kategoriálního součinu.
Řešení 2.3. Sjednocení přes systém množin je definováno jako množina všech
prvků, které leží v některé z množin tohoto systému. Je-li tento systém prázdný,
neobsahuje žádné množiny, ve kterých by prvky mohly ležet, proto je toto sjednocení
prázdné.
Řešení 2.4. Průnik systému množin je definován jako množina všech prvků,
které leží v každé množině daného systému. Je-li však tento systém prázdný,
každá jeho množina splní naprosto cokoliv (neboť žádná taková neexistuje),
zejména obsahuje všechny prvky množiny A. Proto je průnik prázdného systému
roven A. Všimněme si, že je zde podstatný fakt, že uvažujeme podmnožiny
libovolné, ale fixní množiny A. Pokud bychom se ptali pouze na průnik prázdného
systému bez jakéhokoli kontextu, nebyl by výsledek definován, protože
neexistuje nic jako „množina všech prvků“.
Řešení 2.5. Pokud nějaké zobrazení h : A B → C splňuje h ◦ iA = f a
h ◦ iB = g, pak pro všechna a ∈ A musí platit h(iA(a)) = f(a) a pro všechna
b ∈ B musí platit h(iB(b)) = g(b), tedy h((1, a)) = f(a) a h((2, b)) = g(b)
pro všechna a ∈ A, b ∈ B, což korektně definuje zobrazení h. Na druhou stranu
takto definované zobrazení h obě podmínky splňuje, takže je jednoznačně určené.
(Všimněte si, že tato úloha je „duální“ k úloze 2.2 – diagramy vypadají téměř
stejně, jen se změnil směr šipek).
6
2 MNOŽINY
C
A B
A B
f g
iA iB
h
Obr. 2: Diagram kategoriálního součtu.
Řešení 2.6.
a) Neplatí.
b) Platí. Prázdná množina je podmnožinou každé množiny.
c) Neplatí.
d) Neplatí.
e) Neplatí.
f) Platí.
g) Neplatí. Uvažme A = {2}, B = {{2}}, C = {{{2}}}.
h) Neplatí. Uvažme A = ∅, B ⊆ A, B = ∅, C = ∅.
i) Neplatí. „Odečtením“ prázdné množiny se daná množina nikdy nemění.
j) Platí.
k) Platí.
l) Neplatí.
m) Platí.
Řešení 2.7. Platí P(∅) = {∅} a P({∅}) = {∅, {∅}}. Proto musí v právě jedné z
inkluzí ze zadání nastat rovnost. Protože navíc požadujeme {∅} ∈ A, dostáváme
A = {∅}.
Řešení 2.8.
a) {p ∈ N | p je prvočíslo},
b) {22n
| n ∈ N ∪ {0}},
c) {2n
− 1 | n ∈ N},
d) {n ·
n−1
k=0 10k
| n ∈ {1, 2, . . . , 9}},
e) {n ·
n−1
k=0 10k
| n ∈ N}.
7
3 ZOBRAZENÍ A MOHUTNOST MNOŽIN
3 Zobrazení a mohutnost množin
Řešení 3.1.
a) Každé zobrazení f : X → Y můžeme napsat jako složení surjekce na
jeho obraz a inkluze tohoto obrazu do Y . Formálně, definujme zobrazení
h : X → f(X) a g : f(X) → Y předpisy h(x) = f(x) a g(y) = y, potom
platí f = g ◦ h.
4
3
2
1
X
d
c
a
f(X)
d
c
b
a
Y
h g
Obr. 3: Příklad zobrazení f jako složení surjekce a injekce.
b) Nejdříve zkusme uvážit h jako identitu na množině X (ta je určitě injektivní)
a položit g = f. Pokud je f surjektivní, jsme hotovi. V opačném
případě můžeme uvážit množinu Y \ f(X) (tedy množinu složenou z
prvků Y , na které se nic nezobrazilo). Protože množina Y \ f(X) nemusí
být obecně disjunktní s X, uvažme její „kopii“ W (tj. existuje bijekce
k : W → Y \ f(X)), která je disjunktní s X. Položíme-li nyní Z = X ∪ W,
můžeme definovat h : X → Z předpisem h(x) = x a g : Z → Y definujme
pomocí dvou zúžení g|X = f a g|W = k.
4
3
2
1
X
4
3
2
1
X
d
c
b
a
Y
h g
Je-li f surjektivní.
4
3
2
1
X
4
3
2
b
1
Z
d
c
b
a
Y
h g
Není-li f surjektivní, W = {b }.
Obr. 4: Příklad zobrazení f jako složení injekce a surjekce.
8
3 ZOBRAZENÍ A MOHUTNOST MNOŽIN
Řešení 3.2.
a) Diagram nedefinuje funkci, neboť existuje prvek z množiny X, který se na
nic nezobrazuje.
b) Diagram definuje funkci f : X → Y (každý prvek z množiny X se zobrazí
na právě jeden prvek z množiny Y ) . Navíc f je surjektivní, ale není
injektivní.
c) Diagram nedefinuje funkci, neboť existuje prvek z množiny X, který se
zobrazí na dva různé prvky z množiny Y .
d) Diagram definuje funkci f : X → Y (analogicky jako v bodě b)). Funkce
f je injektivní, ale není surjektivní.
Řešení 3.3.
a) R není zobrazením, protože student může studovat na více univerzitách
současně.
b) R je zobrazením, studentův věk je určen jednoznačně.
c) R je zobrazení, právě když všichni studenti mají právě jednoho partnera
či partnerku.
Řešení 3.4.
a) Platí
f−1
i∈I
Ai = x ∈ X | f(x) ∈
i∈I
Ai
= {x ∈ X | ∀i ∈ I : f(x) ∈ Ai}
= x ∈ X | ∀i ∈ I : x ∈ f−1
(Ai)
=
i∈I
f−1
(Ai).
b) Platí
f−1
i∈I
Ai = x ∈ X | f(x) ∈
i∈I
Ai
= {x ∈ X | ∃i ∈ I : f(x) ∈ Ai}
= x ∈ X | ∃i ∈ I : x ∈ f−1
(Ai)
=
i∈I
f−1
(Ai).
Mohutnost množin
Řešení 3.5.
a) Prvky A, B ∈ P spolu leží v jádře, právě když |A| = |B|, tj. množiny A a
B mají stejnou mohutnost.
9
3 ZOBRAZENÍ A MOHUTNOST MNOŽIN
b) Třídy rozkladu P/Jf jsou tvořeny právě množinami se stejnou mohutností,
tím rovnou dostáváme požadovanou bijekci g : P/Jf → N0, která každé
třídě přiřadí počet prvků nějaké její množiny (díky konstrukci rozkladu
P/Jf je toto zobrazení definováno korektně).
Řešení 3.6. Uvažme zobrazení f, které každému nezápornému celému číslu přiřadí
jeho zápis v binární soustavě. Snadno lze ověřit, že se jedná o bijekci, takže
množina vrcholů nekonečného binárního stromu je spočetná.
Jiné řešení je zobrazeno na obrázku 5.
∅
0 1
00 01 10 11
...
g
0
1 2
3 4 5 6
...
Obr. 5: Zobrazení binárního stromu na množinu N ∪ {0}.
Řešení 3.7. Hledejme zobrazení f : (a, b) → (c, d) ve tvaru f(x) = kx + l,
kde k, l ∈ R. Toto zobrazení můžeme geometricky interpretovat jako přímku v
rovině (viz obrázek) procházející body [a, c] a [b, d], přitom je jasné, že se jedná
o bijekci. Díky tomu dostáváme soustavu rovnic
c = ka + l,
d = kb + l.
Odtud dopočítáme, že k = d−c
b−a a l = c−ka, celkem tedy f(x) = d−c
b−a (x−a)+c.
R
R
a b
c
d
f
Obr. 6: Přímka zadávající bijektivní zobrazení mezi intervaly (a, b) a (c, d).
Řešení 3.8. Díky předchozímu příkladu a faktu, že relace „mít stejnou mohutnost“
je tranzitivní (neboť složení dvou bijekcí je opět bijekce), stačí najít
bijekci mezi nějakým konkrétním otevřeným intervalem a R. Zvolme např.
f : (−π
2 , π
2 ) → R, přičemž definujme f(x) = arctan x (viz obrázek).
Dalším příkladem může být funkce g : (0, 1) → R, kde
g(x) =
1
x − 2, x ∈ 0, 1
2 ,
2 − 1
1−x , x ∈ 1
2 , 1 .
Bijektivitu f i g lze snadno ověřit.
10
3 ZOBRAZENÍ A MOHUTNOST MNOŽIN
x
y arctan(x)
Obr. 7: Graf funkce arctan zadávající bijekci mezi (−π
2 , π
2 ) a R.
Řešení 3.9. Pro všechny podbody platí
A ÷ B = (A ∪ B) \ (A ∩ B).
a) Množina A musí být spočetná. Víme totiž, že průnik A ∩ B je konečný.
Pokud by nyní A byla konečná, byla by konečná i množina (A ∪ B) \
\ (A ∩ B). Podobně pokud by A byla nespočetná, byla by nespočetná i
(A ∪ B) \ (A ∩ B).
b) Množina A musí být konečná nebo spočetná. V opačném případě by průnik
A ∩ B byl nejvýše spočetný, a tedy množina (A ∪ B) \ (A ∩ B) by musela
být nespočetná.
c) Množina A musí být nespočetná. V opačném případě by průnik A ∩ B
byl nejvýše spočetný, a tedy množina (A ∪ B) \ (A ∩ B) by musela být
nespočetná.
11
4 RELACE
4 Relace
Řešení 4.1. Uvědomme si, že každá relace na množině A je jednoznačně určena
výběrem uspořádaných dvojic prvků z A a naopak každý takový výběr jednoznačně
určuje relaci. Protože prvky v dané dvojici vybíráme nezávisle na sobě,
je počet takových dvojic |A|2
, a tedy počet všech relací na množině A je 2|A|2
.
Řešení 4.2.
a) Protože počet r všech relací na konečné množině A je konečný (konkrétně
2|A|2
, jak víme z předchozího příkladu), můžeme uvážit postupně relace
R1
, R2
, . . . , Rr+1
.
Z Dirichletova principu nyní vyplývá, že alespoň dvě z těchto relací jsou
stejné.
Naopak je-li A nekonečná, uvedeme protipříklad. Buď A = N a relace
R = {(k, k + 1) | k ∈ N}. Pak pro libovolné n ∈ N platí Rn
= {(k, k +
+ n) | k ∈ N}, tedy pro libovolná n, m ∈ N, n = m platí Rn
= Rm
.
b) Nechť například A = {a, b} a R = {(a, b), (b, a)}, potom
R2k
= {(a, a), (b, b)},
ale R2k+1
= R pro všechna k ∈ N, neboť R pouze oba prvky permutuje.
R R R
b
a
Obr. 8: Příklad relace R, R = R3
= R2
.
Řešení 4.3.
a) R je reflexivní, právě když pro každé a ∈ A platí (a, a) ∈ R, což je přesně
to, že ∆A ⊆ R.
b) R je symetrická, právě když pro všechny dvojice (a, b) ∈ R platí (b, a) ∈ R,
což nastane právě když R = R−1
.
c) Pro (a, b) ∈ R ∩ R−1
platí (b, a) ∈ R ∩ R−1
, inkluze R ∩ R−1
⊆ ∆A pak
znamená, že a = b, což nastane, právě když R je antisymetrická relace.
d) Z vlastnosti skládání zobrazení plyne následující ekvivalence:
R2
= R ◦ R ⊆ R ⇐⇒ ∀a, b, c ∈ A : (((a, b), (b, c) ∈ R) =⇒ (a, c) ∈ R),
přičemž napravo je podmínka ekvivalentní tranzitivnosti R.
e) Začneme implikací zleva doprava. Předpokládejme, že R je reflexivní a
antisymetrická. Potom zřejmě i R−1
je reflexivní a antisymetrická a tak i
jejich průnik musí být reflexivní. Tedy R ∩ R−1
⊇ ∆A. Předpokládejme,
12
4 RELACE
že aR ∩ R−1
b, tedy současně aRb a aR−1
b, což je ekvivalentní s aRb a
bRa, z čehož pro antisymetrii R plyne a = b. A tedy R ∩ R−1
= ∆A.
Nyní půjdeme naopak. Předpokládáme, že R ∩ R−1
= ∆A. Je zřejmé,
že R i R−1
jsou reflexivní. Stačí ukázat, že R je antisymetrická, z čehož
plyne rovněž antisymetričnost R−1
. Pro tyto potřeby nechť a, b ∈ A jsou
libovolné takové, že aRb a bRa. Proto také aR−1
b a bR−1
a. Tedy aR∩R−1
b
a bR ∩ R−1
a. Z antisymetričnosti diagonály dostáváme ihned a = b, což
jsme chtěli ukázat.
Řešení 4.4. Všimněme si, že antisymetričnost je speciální případ acykličnosti
pro n = 2. Uvažme nyní relaci R1 = R ∪ ∆A, kde ∆A = {(a, a) | a ∈ A}.
Vidíme, že R1 je reflexivní a antisymetričnost se zřejmě zachovává (acykličnost
ovšem z triviálních důvodů nikoli). Dále uvažme tranzitivní obal T relace R1
(je definován přepisem T = i∈N Ri
1 a jedná se o nejmenší tranzitivní relaci
obsahující R1 vzhledem k inkluzi). Ten je opět reflexivní, zbývá ukázat, že se
neporušila ani antisymetričnost. Předpokládejme tedy, že aTb a zároveň bTa
pro nějaká a, b ∈ A. Pak podle definice T existují prvky a = a1, a2, . . . , ak = b =
= b1, b2, . . . , bl = a takové, že a1Ra2, . . . , ak−1Rak, b1Rb2, . . . , bl−1Rbl. Odtud
ovšem plyne a = b, jinak bychom dostali spor s acykličností R.
Řešení 4.5.
a) aR−1
b znamená, že a je dítětem b.
b) S−1
= S
c) a(R ◦ S)c znamená, že a je strýc nebo teta osoby c.
d) a(S ◦ R)c znamená, že a je rodičem nějakého sourozence osoby c.
e) aR2
b znamená, že a je prarodičem b.
f) aS2
b znamená, že a = b nebo jsou to sourozenci. V obou případech ale
musí mít společného sourozence.
Řešení 4.6.
a) sym.
b) ref., sym., tranz., jde tedy o relaci ekvivalence
c) antisym., tranz.
d) ref., antisym., tranz.
e) ref., sym., tranz., jde tedy o relaci ekvivalence
f) ref., sym.
g) sym.
h) Buď R = ∅ =⇒ sym., antisym., tranz. A nebo: R = R2
=⇒ ref., sym.,
tranz.
Řešení 4.7. P i S jsou reflexivní, symetrické a tranzitivní. Obě jsou tedy ekvi-
valence.
13
4 RELACE
Řešení 4.8. Relace R je reflexivní, neboť každý stát má sám se sebou společnou
hranici. Je zřejmě symetrická. Tato relace není tranzitivní, neboť např. Česká
republika a Francie nesdílí žádnou část hranice, i když obě sousedí s Německem.
Řešení 4.9. Nejprve si uvědomme, že poloha hodinové ručičky jednoznačně přiřazuje
polohu ručičky minutové. Proto je ρ skutečně zobrazení. Není ale prosté,
protože dané poloze dlouhé ručičky odpovídá hned 12 růných poloh malé ručičky.
Proto ρ−1
není zobrazení. Je to relace na [0, 2π)2
, určená (β, α) ∈ ρ−1
tehdy, když existuje denní čas, kdy ú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 β.
Řešení 4.10. Na prvky ρ se můžeme dívat jako na matice typu 2×2 nad reálnými
čísly. chápeme-li prvek ((a, b)(c, d)) ∈ ρ jako matici a b
c d , potom výraz ad −
− bc odpovídá determinantu této matice. Můžeme tak využít znalosti z lineární
algebry.
a) Matice složená ze dvou stejných řádků má nulový determinant, takže ρ
není reflexivní. Prohození dvou řádků matice mění pouze znaménko determinantu,
ale jeho absolutní hodnota se nemění, tedy ρ je symetrická.
Tranzitivní relace ρ není, např.
det
1 1
0 1
= 1 = det
0 1
1 1
,
ale
det
1 1
1 1
= 0.
Relace ρ není ani antisymetrická, protože např.
det
1 0
0 1
= det
0 1
1 0
.
b) Relace ρ je reflexivní, protože matice složená ze dvou stejných řádků má
nulový determinant. Dále je ρ symetrická, neboť záměna řádků pouze mění
znaménko nulového determinantu. Tranzitivita ρ plyne ze známého faktu,
že matice má nulový determinant, právě když jsou její řádky lineárně
závislé, což v případě matic typu 2 × 2 znamená, že jeden je nenulovým
skalárním násobkem druhého, a toho že relace být nenulovým skalárním
násobkem je tranzitivní. Antisymetrická není, neboť např.
det
1 0
0 0
= det
0 0
1 0
.
Řešení 4.11. Relace ρ není reflexivní, neboť žádný člověk není o rok starší než
on sám. Také není symetrická, protože určitě existují dva lidé, z nichž jeden je
o rok starší než druhý, ale ne naopak. Dále není tranzitivní, neboť je-li B o rok
starší než A a zároveň C o rok starší než B, je C o dva roky starší než A, nikoli
o jeden. Antisymetrická ovšem je, neboť neexistují žádní dva lidé, z nichž by
každý byl o rok starší než druhý, takže z tohoto předpokladu vyplývá libovolné
tvrzení, zejména pak, že tito lidé jsou totožní.
14
4 RELACE
Řešení 4.12. Relace ρ není reflexivní, neboť určitě existuje alespoň jeden člověk,
který sám sebe neobdivuje. Také není symetrická, protože určitě existují
dva lidé, z nichž jeden obdivuje druhého, ale ne naopak. Dále není tranzitivní,
neboť určitě existují tři lidé, z nichž jeden obdivuje druhého a druhý třetího,
ale nikoliv první třetího. Antisymetrická také není, protože určitě existují dva
různí lidé, kteří se vzájemně obdivují. (Pro konkrétní případy výše uvedených
tvrzení proveďte důkladný rozbor rodin autorů této sbírky.)
Řešení 4.13. Relace ρ je reflexivní, právě když n = 1. Symetrická je pro všechna
n ∈ N. Tranzitivní je právě pro n = 1 (už kvůli tomu, že je symetrická a současně
pro n = 1 není reflexivní). Antisymetrická je právě pro n = 1, neboť pro n > 1
stačí uvážit libovolné dva sousedy.
Řešení 4.14. Žádná z relací R, S není reflexivní, neboť žádný ze studentů nehrál
sám se sebou páku, tedy nad sebou zejména nevyhrál. Relace R je symetrická,
zatímco S ne. Relace R je tranzitivní, neboť každý student hrál s každým. O
tranzitivitě S neumíme rozhodnout, neboť záleží na výsledcích utkání. Relace
R není antisymetrická, avšak relace S ano, neboť žádní dva různí studenti se
nemohli navzájem porazit.
Řešení 4.15.
a) Zadání vyhovuje např. V = {(a, a)} (viz obrázek).
b) Zadání vyhovuje např. V = {(a, b), (b, a)} (viz obrázek).
c) Zadání vyhovuje např. V = {(a, b), (b, a), (c, d)} (viz obrázek).
V V V
a
b
c
d
1.
V V V
a
b
c
d
2.
V V V V
a
b
c
d
3.
Obr. 9: Příklady relací.
Řešení 4.16.
a) Zadání vyhovuje např. V = {(a, b)} (viz obrázek).
b) Zadání vyhovuje např. V = {(a, b), (c, a)} (viz obrázek).
V V
a
b
1.
V V V
a
b
c
2.
Obr. 10: Příklady relací.
15
4 RELACE
Řešení 4.17. Zadání vyhovují např. relace U = {(a, b)}, V = {(a, a), (b, b)} a
W = {(a, a)} (viz obrázek).
V U
W U
a
b
a
b
Obr. 11: Příklad relací U, V .
Řešení 4.18.
a) Neplatí, uvažme např. V = {(a, a), (b, b)}, U = {(a, a), (b, b), (a, b)}.
b) Nechť (a, b) ∈ V , pak také (a, b) ∈ U ◦ V , neboť z reflexivity U plyne
(b, b) ∈ U. Proto platí V ⊆ U ◦ V .
Řešení 4.19. Zadání vyhovuje např. množina A = {1, 2, . . . , n} a relace
R = {(k, k + 1) | k ∈ {1, . . . , n − 1}} ∪ {(n, n)}
a platí Rk
= Rl
pro l < k < n, ale Rk
= Rl
pro n − 1 ≤ k < l (viz obrázek).
Pro n = 4 dostáváme
R R R R
1
2
3
4
Obr. 12: Příklad relace R pro n = 4.
Řešení 4.20.
a) Je reflexivní a tranzitivní, není symetrická ani antisymetrická.
b) Je nutné přidat šipky c → b, c → a, což zároveň stačí.
c) Je nutné smazat jednu ze šipek a → b nebo b → a, což zároveň stačí.
Řešení 4.21. Všechny hledané relace musí být reflexivní, tudíž každá obsahuje
všechny dvojice tvaru (x, x), x ∈ N. Kdyby dále některé z nich obsahovala dvojici
(y, z), y, z ∈ N, y = z, pak by kvůli podmínce symetrie obsahovala také dvojici
(z, y), takže z antisymetrie by plynulo y = z, což je spor. Proto zadání vyhovuje
pouze jediná relace {(x, x) | x ∈ N}. (Uvědomme si, že stejnou úvahu bychom
mohli provést nejen pro množinu N, ale pro libovolnou množinu.)
16
5 USPOŘÁDANÉ MNOŽINY
5 Uspořádané množiny
Řešení 5.1.
a) Předpokládejme, že existuje supremum množiny všech prvočísel a označme
jej p. Tedy p je dělitelné každým prvočíslem, tedy je větší rovno každému
prvočíslu. To je spor s tím, že je prvočísel nekonečně mnoho, protože existuje
pouze konečně mnoho prvočísel nepřesahujících p. Sporem jsme ukázali,
že tvrzení neplatí.
b) Supremem prázdné množiny je zde nejmenší prvek 1. Supremum každé
konečné neprázdné podmnožiny N je zase nejmenší společný násobek jejích
prvků. Tvrzení platí.
c) Označme s nejmenší přirozené číslo (v obvyklém uspořádání) dané neprázdné
podmnožiny A přirozených čísel. Každá dolní závora množiny A
v uspořádání dělitelnosti musí zejména dělit číslo s. Jistě je číslo jedna
dolní závorou množiny A v uspořádání dělitelnost (1 dělí každé číslo z A).
Je proto množina všech dolních závor množiny A neprázdná a konečná.
Má tedy největší prvek a ten je infimem A.
d) Plyne z předešlých dvou částí - každá dvouprvková podmnožina má supremum
i infimum.
Řešení 5.2. Uvažme rozklad na prvočinitele čísla k = pa1
1 pa2
2 . . . pan
n , n ∈ N0, kde
a1, · · · , an ∈ N. Bezprostředně pod číslem k se v našem diagramu nalézají právě
čísla tvaru pa1−1
1 pa2
2 . . . pan
n , pa1
1 pa2−1
2 . . . pan
n , . . . , pa1
1 pa2
2 . . . pan−1
n , kterých je n.
1
2 3 5 7 . . .
4 6 9 10 14 15 21 25 35 49 . . .
... ...
Obr. 13: Hasseův diagram pro přirozená čísla uspořádaná dělitelností.
Řešení 5.3.
a) Ano, existuje. Například uvažme standardní uspořádání na množině N a
uspořádání tvaru 1, 3, 5, . . . , 2, 4, 6, . . . (tedy nejdříve všechna lichá čísla,
poté všechna sudá čísla uspořádaná podle velikosti viz obrázek 14). Druhé
uspořádání lze formálně popsat takto
x y ⇐⇒ (2 | x − y ∧ x ≤ y) ∨ (2 x ∧ 2 | y)
b) Ano, existuje. Opět využijeme dělitelnosti. Pro každé n ∈ N, definujeme
uspořádání
x n y ⇐⇒ (n | x − y ∧ x ≤ y) ∨ (r(x) ≤ r(y)),
17
5 USPOŘÁDANÉ MNOŽINY
1
3
5
...
2
4
6
...
Obr. 14: Hasseův diagram množiny přirozených čísel uspořádaných podle .
kde r(x) značí zbytek čísla x po dělení číslem n. (Jde o zobecnění principu
použitého v předchozím bodě.)
c) Tvrzení výplývá z faktu, že lineární uspořádání N odpovídají spočetným
ordinálním číslům, kterých je nespočetně mnoho. Je také možné explicitně
zkonstruovat nespočetně mnoho vzájemně neizomorfních uspořádání N,
ale to je poněkud složitější.
Řešení 5.4. Víme, že každá podmnožina množiny (A, ≤) má supremum. Vidíme,
že A má největší prvek - je jím supremum celé množiny A. Největší prvek
množiny A je pak infimem prázdné množiny. Buď B ⊆ A neprázdná množina.
Chceme ukázat, že má v A infimum. Buď U množina všech dolních závor množiny
B, tj.
U = {u ∈ A : ∀b ∈ Bu ≤ b}.
Množina U jistě obsahuje nejmenší prvek množiny A a je tak neprázdná.
Její supremum označíme m. Pokud ukážeme, že m ∈ U, bude m největší dolní
závorou množiny B, tedy jejím infimem. Pro libovolné b ∈ B platí x ≤ b pro
každé x ∈ U. Proto b je horní závora množiny U. Ale m je jejím supremem,
takže m ≤ b (m je nejmenší horní závora U). To ale platí pro všechna b ∈ B a
proto m ∈ U.
Řešení 5.5.
a) Zvolme zobrazení f : (X, ) → (P(X), ⊆) definované předpisem f(¯x) =
= {x ∈ X|x ≤ ¯x}. Toto zobrazení je zřejmě prosté a má požadovanou
vlastnost x1 x2 ⇔ f(x1) ⊆ f(x2).
b) Nakreslíme si Hasseův diagram dané konečné uspořádané množiny X. Ta
má konečně mnoho minimálních prvků a ty zobrazíme na libovolná různá
prvočísla. V každém dalším kroku škrtneme minimální prvky v našem
diagramu a zaměříme se na minimální prvky takto vzniklého diagramu.
Takový prvek x zobrazíme na nejmenší společný násobek jeho předchůdců
(tj. právě škrtnutých minimálních prvků, které jsou pod x). Protože je
X konečná množina, je konečný i tento algoritmus. Snadno nahlédneme,
že s ohledem na jednoznačnost rozkladu na prvočinitele je toto zobrazení
prosté.
18
5 USPOŘÁDANÉ MNOŽINY
E0
E1 E2 E3
E4
c) Myšlenka možného řešení spočívá ve využití následující vlastnosti racionálních
čísel: mezi každými dvěma racionálními čísly existuje spočetně mnoho
dalších racionálních čísel (která jsou samozřejmě opět lineárně uspořádaná)
- stačí půlit intervaly. Protože i mezi libovolnými dvěma prvky libovolné
nejvýše spočetné uspořádané množiny existuje nejvýše konečně
mnoho prvků (v daném uspořádání), je možno hledané vnoření sestrojit.
Řešení 5.6.
a) Označme X = {1, 2, 3}. Z podmínky reflexivity obsahuje každá ekvivalence
E ∈ Eq(X) nutně všechny prvky tvaru (x, x) pro x ∈ X. Přičemž symetrie
i tranzitivita jsou splněny, dostáváme tak rovnou jednu ekvivalenci E0 =
= {(1, 1), (2, 2), (3, 3)}.
Pokud přidáme prvek (x, y), kde x = y musíme kvůli zachování symetrie
přidat i (y, x), tranzitivita je přitom splněna. Dále tedy získáváme E1 =
= E0 ∪{(1, 2), (2, 1)}, E2 = E0 ∪{(2, 3), (3, 2)} a E3 = E0 ∪{(1, 3), (3, 1)}.
Přidání libovolné další dvojice (u, v), kde u = v, kterou jsme zatím nepoužili,
vynutí přidání již všech dvojic. Tedy E4 = X × X. Se znalostí všech
ekvivalencí na X již není těžké nakreslit Hasseův diagram pro (Eq(X), ⊆).
b)
Důkaz 1 Stačí ukázat, že každá dvojprvková podmnožina P = {σ, ρ} uspořádané
množiny Eq(X), má supremum a infimum. Uvažme průnik
relací σ ∩ρ. Ukážeme-li, že je to ekvivalence, bude jasné, že je to také
infimum P.
Reflexivní je, neboť obě relace ρ a σ jsou reflexivní a obsahují tedy
diagonálu {(x, x), x ∈ X}, která tak leží i v jejich průniku.
Symetrie je také jednoduchá: Nechť (x, y) ∈ σ ∩ ρ, pak
(x, y) ∈ σ ∧ (x, y) ∈ ρ.
Ze symetrie obou relací dostáváme (y, x) ∈ σ ∧ (y, x) ∈ ρ. Proto
(y, x) ∈ σ ∩ ρ.
Zbývá ukázat, že je σ ∩ρ tranzitivní. Nechť tedy (x, y), (y, z) ∈ σ ∩ρ.
Potom z tranzitivity obou relací σ a ρ plyne (x, z) ∈ σ ∩ ρ.
Nyní najdeme supremum množiny {σ, ρ}. Každá horní závora {σ, ρ}
musí obsahovat všechny prvky σ a ρ. Tedy i naše supremum musí být
minimálně σ ∪ ρ. Všimněme si, že σ ∪ ρ podobně jako průnik „dědí“
vlastnosti symetrii a reflexivitu. Bohužel však nemusí být tranzitivní.
Uvažme tranzitivní obal (σ ∪ ρ)+
. Ten je definován jako průnik systému
T všech tranzitivních relací, které obsahují σ ∪ ρ jako svoji
19
5 USPOŘÁDANÉ MNOŽINY
podmnožinu. Systém T je vždy neprázdný, jelikož v něm leží celá
2X
. Zřejmě je (σ ∪ ρ)+
nejmenší tranzitivní relace obsahující (σ ∪ ρ).
Její reflexivita je zřejmá. Zbývá ukázat, že je také symetrická. Systém
T je uzavřený na inverzní relace (inverze tranzitivní relace je tranzitivní
a σ ∪ ρ je symetrická). Proto je průnik jeho prvků invariantní
vůči inverzi a tedy symetrický.
Důkaz 2 Ukážeme něco ještě silnějšího, totiž, že se jedná o úplný svaz. Stačí
ukázat, že libovolná podmnožina P uspořádané množiny Eq(X), má
infimum. To bude průnikem všech prvků P, který si zachová symetrii,
reflexivitu i tranzitivitu, což necháváme jako cvičení. Na těchto dvou
důkazech je hezky vidět, že někdy může být snazší dokazovat něco
silnějšího, než se po nás ve skutečnosti žádá - je jen potřeba si toho
všimnout.
Řešení 5.7.
a) Ano, existuje. Podmínky splňuje:
Každý z prvků je maximální a musejí být minimálně dva, což zároveň
stačí.
b) Ano, existuje. Podmínky splňuje:
Pokud bychom odebrali prvek z „dolního patra“ nebude uspořádání splňovat
podmínku existence množiny bez infima. Naopak odebrání prvku z
„horního patra“ poruší podmínku existence suprema. Odebráním libovolných
dvou prvků zůstane pouze jeden prvek, opět se ale poruší podmínka
existence množiny bez infima.
c) Neexistuje. Postupujme sporem. Předpokládejme existenci dvou největších
prvků n1, n2, přičemž n1 = n2. Protože jsou oba největší, platí n1 ≤
≤ n2 ≤ n1, a protože jde o uspořádání (zejména platí antisymetrie), pak
n1 = n2, což je spor.
d) Ano, existuje. Podmínky splňuje (kde levý řetězec je nekonečný):
...
Začněme jedním prvkem. Ten je určitě minimální, zároveň však nejmenší.
Abychom porušili druhou vlastnost je třeba přidat jiný, nesrovnatelný
prvek. Nyní se ale nacházíme v situaci z bodu 1., musíme proto přidat
celý nekonečný řetězec, abychom zaručili neexistenci druhého minimálního
prvku.
20
5 USPOŘÁDANÉ MNOŽINY
Řešení 5.8. Na obrázku vidíte všechny šestiprvkové svazy.
Obr. 15: Všechny šestiprvkové svazy.
Řešení 5.9. Každé takové izotonní zobrazení jednoznačně odpovídá m-prvkové
kombinaci s opakováním vybrané z n prvkové množiny. Těch je přitom n+m−1
m .
Řešení 5.10. Izomorfismus je bijekce zachovávající uspořádání oběma směry.
Předpokládejme pro spor, že existuje izomorfismus z úplného svazu všech podmnožin
dvouprvkové množiny do čtyřprvkového řetězce. Největší prvek musí jít
na největší prvek, nejmenší na nejmenší a zbylé dva musíme zobrazit vedle sebe.
A máme tu kýžený spor, protože dva porovnatelné prvky se nám zobrazily na
dva prvky nesrovnatelné.
∅
{a}
{a, b}
{b}
Obr. 16: Neexistence izomorfismu mezi danými uspořádáními.
Řešení 5.11.
a) Ukážeme, že se skutečně jedná o úplný svaz. Prázdná množina má zřejmě
supremum, což je nejmenší prvek množiny II
, tj. konstantní zobrazení na
nulu. Každá neprázdná množina A má supremum, které zobrazí x ∈ I na
sup{f(x), f ∈ A}, přičemž sup{f(x), f ∈ A} existuje, neboť reálná čísla
jsou úplným svazem.
b) Množina H := {f : I → I, f(x) = xn
|n ∈ N} všech mocninných funkcí
nemá supremum. Nejde tedy o úplný svaz, ale svaz to je.
21
5 USPOŘÁDANÉ MNOŽINY
c) Označme f, g : I → I, f(x) = x, g(x) = 1 − x. Množina {f, g} pak nemá
supremum a nejde tedy o svaz, natož úplný svaz.
d) Nejde o úplný svaz. Množina H z bodu b) zde totiž opět nemá supremum.
e) Dokažme, že se jedná o úplný svaz. Prázdná množina má zřejmě supremum
konstantní zobrazení na nulu, které je neklesající. Každá neprázdná
množina A neklesajících funkcí I → I má supremum, které zobrazí x ∈ I
na sup{f(x), f ∈ A}, přičemž sup{f(x), f ∈ A} existuje, neboť reálná
čísla jsou úplným svazem, a je neklesající.
Řešení 5.12. Abychom ukázali, že relace ≤ ze zadání je skutečně relací uspořádání
potřebujeme ověřit, že je ≤ reflexivní, tranzitivní a antisymetrická. Každou
římskou číslici vytvoříme z ní samotné přiložením nula sirek, tedy ≤ je reflexivní.
Nechť dále y vznikne z x přiložením k ≥ 0 sirek a z vznikne z y přiložením l ≥ 0
sirek (tedy x ≤ y a zároveň y ≤ z), potom z vznikne z x přiložením k + l sirek
(tj. x ≤ z), přičemž zřejmě k + l ≥ 0, a proto platí tranzitivita ≤. Antisymetrii
dokažme sporem, nechť tedy x ≤ y a zároveň y ≤ x, tedy y vznikne z x přidáním
k ≥ 0 sirek, a následně přidáním l ≥ 0 dostaneme opět x. Dohromady x
vznikne z x přidáním k + l ≥ 0 sirek, kdyby x = y, pak alespoň jedno z čísel
k, l je kladné. A to je spor, protože žádné římské číslo nevznikne samo ze sebe
přidáním kladného počtu sirek.
I
II
III
V
IV VI
VII
VIII
X
XI
Obr. 17: Hasseův diagram uspořádání sirek.
Řešení 5.13.
a) Izotonní zobrazení existuje – stačí zvolit vnoření f : Z \ N → Z definované
f(z) = z. Izomorfismus ale neexistuje, neboť by musel zobrazit největší
prvek 0 množiny Z \ N na největší prvek. Žádný takový ale množina Z
neobsahuje.
b) Izotonní zobrazení existuje – stačí zvolit triviální zobrazení f : N → Z\{0}
definované f(z) = 1. Izomorfismus opět neexistuje, protože by zobrazení
f−1
muselo zobrazit největší prvek 1 množiny Z \ {0} na největší prvek.
Žádný takový, ale v (N, ) neexistuje.
Uvědomme si, že mezi libovolnými dvěma uspořádanými množina existuje
takovéto triviální izotonní zobrazení vždy. V tomto případě však neexistuje
žádné vnoření.
22
6 EKVIVALENCE
6 Ekvivalence
Řešení 6.1. U některých příkladů navíc udáváme pro lepší představu příklad
množiny, se kterou je daný rozklad Dom(f)/Jf v bijekci.
a) Každý den si označme jeho pořadím v přestupném roce. Hledaným rozkladem
je množina tříd lidí, kteří mají narozeniny ve stejný den v roce.
b) Hledaným rozkladem je množina {{kruh}, {trojúhelník}, {čtverec, obdélník}},
což je trojprvková množina.
c) Hledaným rozkladem je množina {{−x, x} | x ∈ R}, která je v bijekci s
R+
0 .
d) Hledaným rozkladem je množina {x + 7Z | x ∈ {0, . . . , 6}}, kde x + 7Z =
= {x + 7k | k ∈ Z}. Tato množina se nazývá množina zbytkových tříd
modulo 7, značí se Z7 a je sedmiprvková.
e) Hledaným rozkladem je množina tříd zlomků, které mají stejný základní
tvar, což je v bijekci s množinou {p
q | p ∈ Z, q ∈ N, gcd(p, q) = 1} =
= {p
q | p ∈ Z, q ∈ N} = Q.
f) Uvědomme si, že rovnice x2
+ y2
= r2
, r ∈ R+
0 popisuje kružnici v rovinně
se středem v počátku o poloměru r. Dva různé body (u, v), (x, y) ∈ R × R
jsou tedy ve stejné třídě rozkladu, právě když leží na stejné kružnici se
středem v počátku.
x
y
...
...
...
...
Obr. 18: Rozklad R × R podle Jf .
g) Pro dva prvky (u, v), (x, y) ∈ R × R platí (u, v) ∼ (x, y), právě když
|u − x| ∈ [0, 1). Rozkladem je tak množina {Pk | k ∈ Z}, kde Pk =
= {(x, y) ∈ R × R | k ≤ x < k + 1} (viz obrázek).
23
6 EKVIVALENCE
x
y
P−3
−3
P−2
−2
P−1
−1
P0
0
P1
1
P2
2
P3
3
. . .
. . .
. . .
. . .
Obr. 19: Rozklad R × R podle Jf .
Řešení 6.2. Uvědomme si, že každé rýmové schéma odpovídá výběru řádků,
které se navzájem rýmují (všimněme si, že „rýmovat se“ je relace ekvivalence).
Tudíž každé rýmové schéma n-řádkové básně odpovídá počtu ekvivalencí na n-prvkové
množině (tento počet se nazývá n-té Bellovo číslo). Snadno ověříme,
že na čtyřprvkové množině existuje 15 ekvivalencí, a tedy i rýmových schémat.
Jsou to právě tyto: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB,
ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC aligned ABCD.
Řešení 6.3. To že jde o ekvivalenci ověříme snadno ve třech krocích:
a) Reflexivita: každé římské číslo je v relaci ρ samo se sebou.
b) Symetrie: Pokud se číslo A skládá ze stejně sirek jako číslo B, tak se určitě
i číslo B skládá ze stejně sirek jako číslo A.
c) Tranzitivita: Pokud se číslo A skládá ze stejně sirek jako číslo B a číslo B
skládá ze stejně sirek jako číslo C, tak se určitě číslo A skládá ze stejně
sirek jako číslo C.
Příslušný rozklad má 5 prvků:
{{I}, {II,V,X}, {III,IV,VI,IX}, {VII}, {VIII}}.
Řešení 6.4.
a) Poslouží nám zobrazení f z množiny všech žáků dané školy do množiny
všech tříd v této škole, které žáka zobrazí na třídu, do níž chodí.
b) Zde uvázíme zobrazení z množiny všech zvířat do N0 tak, že každé zvíře
zobrazíme na počet jeho nohou (hada na nulu).
Řešení 6.5. Nejprve ukážeme, že relace ∼ je ekvivalence:
a) Reflexivita: ∀u ∈ U : u ∼ u ⇐⇒ u − u ∈ ker ϕ, což platí vždy, neboť
ϕ(0) = 0.
b) Symetrie: Protože je ker ϕ lineární podprostor vektorového prostoru U, je
uzavřený na násobení −1. Platí
∀u, v ∈ U : u ∼ v ⇐⇒ u − v ∈ ker ϕ
⇐⇒ −1(u − v) = v − u ∈ ker ϕ
⇐⇒ v ∼ u.
24
6 EKVIVALENCE
c) Tranzitivita:
∀u, v, w ∈ U : u ∼ v ∧ v ∼ w =⇒ u − v, v − w ∈ ker ϕ
=⇒ u − v + v − w ∈ ker ϕ
⇐⇒ u ∼ w.
Protože rovnost ϕ(u) = ϕ(v) je díky linearitě ϕ ekvivalentní rovnosti ϕ(u−v) =
= 0, dostáváme, že Jϕ =∼ .
25
7 KOMBINATORIKA
7 Kombinatorika
Řešení 7.1. Uvažme osmiúhelník jako na obrázku složený z 14 čtverců o stranách
jeden metr. Snadno nahlédneme, že libovolná dvojice bodů tohoto útvaru má
od sebe vzdálenost nejvýše 5 metrů.
Obr. 20: Osmiúhelníkový útvar.
Každý pás pozemku o rozměrech 7 x 24 jsme schopni rozdělit na 13 dílů, z
nichž každý se vejde do našeho osmiúhelníka. Přitom celou zahradu lze pokrýt
šesti takovými pásy.
Obr. 21: Pás vyplněný útvary.
Tak jsme rozdělili dědův pozemek na 6·13 = 78 dílků. Protože stromů je 80,
musí být dle Dirichletova principu alespoň v jednom z dílků alespoň dva stromy.
Ty jsou pak od sebe nejvýše pět metrů daleko.
Řešení 7.2.
a) Každý takový obdélník lze jednoznačně popsat výběrem dvojice svislých
čar a dvojice horizontálních čar, které ho ohraničí. Těch je ale m+1
2 · n+1
2 .
b) Čtverce seřadíme podle velikosti a sečteme zvlášť. Čtverců o straně r je
zde zřejmě (m − r + 1)(n − r + 1). Tedy celkem
min{m,n}
r=1
(m − r + 1)(n − r + 1).
Řešení 7.3. Pokud bychom koně uměli rozlišit, stačilo by sečíst přes všechna
pole počet všech ostatních, ne něž může kůň táhnout. Na obrázku je v každé
poli P šachovnice počet okolních polí, na která lze z P skočit koněm. Součet
4(4 · 8 + 4 · 6 + 5 · 4 + 2 · 3 + 2) = 336 čísel v polích je dvojnásobkem hledaného
počtu, neboť koně jsou nerozlišitelní. Odpověď zní 168.
26
7 KOMBINATORIKA
Řešení 7.4.
a) 7!
7 = 6! = 720
b) Seřadíme je do řady a postupně posadíme. Tedy 7! = 5040.
Řešení 7.5.
a) To je přece polovina všech seřazení, tedy 5!
2 .
b) Jestli má jít A hned po B, můžeme je sloučit dopředu, takže vlastně řadíme
prvky AB, C, D, E. To jde 4! možnostmi.
Řešení 7.6. Všech možných iniciál je 262
= 676. Každý obyvatel tak může mít
svou vlastní iniciálu.
Řešení 7.7. Zajímá nás nejvyšší mocniny dvou a pěti, které dělí 258!. Zřejmě
je exponent u dvojky vyšší než příslušný exponent u pětky. Pěti je dělitelný
každý pátý činitel součinu 258! = 1 · 2 · 3 · · · 258. Tedy je zde 258
5 = 51 činitelů
dělitelných pěti. Dále je zde 258
25 = 10 činitelů dělitelných 25. Nakonec jsou zde
258
125 = 2 činitelé dělitelní 125. Celkem je tedy exponent u pětky v prvočíselném
rozkladu 258! roven 51 + 10 + 2 = 63. To je také počet nul v dekadickém zápise
čísla 258!.
Řešení 7.8. 1. 10
2 , 2. 10
3 , 3. 9
2 .
Řešení 7.9. Nejprve ukážeme, že pro n ≥ k je číslo n!
(n−k)!·k! celé. Stačí si uvědomit,
že je to počet všech k-prvkových podmnožin n-prvkové množiny (n! způsoby
seřadíme celou množinu a vezmeme si prvních k prvků. Tak dostaneme k-prvkovou
podmnožinu, ale na pořadí prvních k prvků a pořadí posledních n − k
prvků nezáleží, protože dávají stejnou podmnožinu.)
Když už teď víme, že n!
(n−k)!·k! = n(n−1)···(n−k+1)
k! je celé číslo, tak po substituci
m = n − k + 1 ∈ N je (m+k−1)(m+k−2)···m
k! stále celým číslem. Tedy pro
každé přirozené m je součin k po sobě jdoucích čísel m počínaje dělitelný k!. To
jsme chtěli dokázat.
Řešení 7.10. Důkaz lze jednoduše provést rozepsáním obou stran pomocí vlastností
kombinačních čísel. Intuitivně tato rovnost znamená, že obě strany rovnosti
vyjadřují počet všech možností, jak vybrat k-prvkový a l-prvkový tým z n lidí
tak, aby nikdo nepatřil do obou týmů.
Řešení 7.11. Vlevo je 2n
2 , což je počet všech dvojic, které lze vybrat z 2n−
−prvkové množniny. Pokud bychom vybírali dvojice tak, že množinu rozpůlíme
na dvě n prvkové množiny a rozlišíme dva případy:
a) Dvojici tvoří prvky ze stejné půlky. Těchto dvojic je n
2 za každou půlku,
celkem tedy 2 · n
2 .
b) Dvojici tvoří prvky z obou skupin. Těchto dvojic je zřejmě n · n.
Celkem tedy 2 · n
2 + n2
. Dokázali jsme požadovanou rovnost.
27
7 KOMBINATORIKA
Princip inkluze a exkluze
Řešení 7.12. Označme M1, . . . , M11 množiny žáků v kroužcích. Podmínky ze zadání
jsou ekvivalentní tomu, že pro všechna po dvou různá i, j, k, l ∈ {1, . . . , 11}
|M1 ∪ . . . ∪ M11| = 54,
|Mi| ≥ 15,
|Mi ∩ Mj ∩ Mk| ≥ 1,
|Mi ∩ Mj ∩ Mk ∩ Ml| = 0.
Podle principu inkluze a exkluze je
|M1∪. . .∪M11| =
11
i=1
|Mi|−
11
i=1
11
j=i+1
|Mi∩Mj|+
11
i=1
11
j=i+1
11
k=i+j+1
|Mi∩Mj∩Mk|,
protože ostatní členy jsou nulové. Proto
54 ≥ 11 · 15 −
11
i=1
11
j=i+1
|Mi ∩ Mj| +
11
3
· 1,
a tedy
11
i=1
11
j=i+1 |Mi ∩ Mj| ≥ 276.
Vlevo je 11
2 = 55 sčítanců a aspoň jeden z nich musí být větší než 5.
Řešení 7.13. 2n n
r=0(−1)r n
r
(2n−r)!
2n−r .
Řešení 7.14. 30
15 − 30
16 .
28
8 GRAFY
8 Grafy
Řešení 8.1. Předpokládejme, že z grafu G vede homomorfismus f do Kk (úplného
grafu na k vrcholech). Označíme-li vrcholy Kk jako V1, V2, . . . , Vk, dostáváme
k disjunktních množin f−1
(V1), f−1
(V2), . . . , f−1
(Vk), jejichž sjednocením
je množina vrcholů G. Obarvíme-li každou z těchto množin různou barvu, dostaneme
(vrcholové) k-obarvení G, protože pokud by některé dva sousední vrcholy
G měly stejnou barvu, musely by se v f zobrazit na stejný vrchol (kvůli konstrukci
obarvení) a zároveň na sousední vrcholy (kvůli definici homomorfismu
– všimněte si, že zde využíváme toho, že graf nesmí obsahovat smyčky, tj. z
žádného vrcholu nevede hrana do něj samého).
Nyní naopak předpokládejme, že G je (vrcholově) k-obarvitelný. Pak můžeme
zkonstruovat zobrazení f : G → Kk tak, že všechny vrcholy i-té barvy zobrazí
f na vrchol Vi pro 1 ≤ i ≤ k. Pak je f homomorfismus, protože pokud libovolné
dva sousední vrcholy G mají různé barvy, tak se zobrazí na různé vrcholy Kk,
což je úplný graf.
Řešení 8.2.
a) Graf je eulerovský právě pro sudá n (využíváme zde parity kombinačních
čísel).
b) Každá hrana spojuje dvě množiny, z nichž právě jedna je sudé kardinality
a druhá liché. Stačí nám tedy dvě barvy, jednou barvou obarvíme všechny
množiny liché kardinality a druhou barvou množiny sudé kardinality.
Řešení 8.3.
a) Graf G není eulerovský, např. vrcholy {3, 5, 8, 9, 10, 11} mají stupeň jedna,
tedy lichý.
b) Graf G je rovinný, jak je patrné z obrázku 22. Hranu mezi vrcholy 2 a 10
můžeme určitě vést tak, aby neprotínala žádnou jinou hranu.
1
2 3 5 7 11
4 6 9 10
8 12
Obr. 22: Rovinné nakreslení grafu.
c) Na obrázku 23 je znázorněno ohodnocení hran, a dále jedna z možných
minimálních koster.
29
8 GRAFY
1
2 3 5 7 11
4 6 9 10
8 12
2 3 5 7 11
2
3
52
3
4
2
3
2
2
Obr. 23: Ohodnocení a minimální kostra grafu.
Řešení 8.4.
a) Graf G není eulerovský, obsahuje vrchol lichého stupně.
b) Graf G je rovinný, jak je zřejmé z obrázku 24.
c) Na obrázku 24 je znázorněno ohodnocení hran, a dále jedna z možných
minimálních koster.
6
7
8
2
6
1
3
5 4 1
26
4
Obr. 24: Rovinnost, ohodnocení a minimální kostra grafu.
Řešení 8.5. Grafy vyhovující zadání jsou čtyři, viz obrázek 25.
Obr. 25: Grafy splňující zadání.
30
8 GRAFY
Řešení 8.6. Celkem chceme, aby se hodnota spočítaná pro vrchol v měnila v
každém kroku. Proto je potřeba „uzavřít“ vrchol v jako poslední. Uvažme příklad
takového grafu i s příslušným výpočtem nejkratších cest.
u4
v
u
u1
u2
u3
1
50 10
5
7
3
5
15
30
u u1 u2 u3 u4 v
0 ∞ ∞ ∞ ∞ ∞
0 10 ∞ ∞ ∞ 50
0 10 15 ∞ ∞ 40
0 10 15 22 ∞ 30
0 10 15 22 25 27
0 10 15 22 25 26
Obr. 26: Dijkstrův algoritmus. Nejkratší cesta se mění v každém kroku.
Řešení 8.7. Vidíme, že například při výpočtu nejkratších cest z vrcholu u vyjde
vzdálenost u, v rovna 6, zatímco při výpočtu nejkratších cest z vrcholu v získáme
délku nejkratší cesty mezi u a v rovnu 7. (Jsou to jediné vrcholy, které můžeme
porovnávat!)
u
u3
v
u2
u1
6
-3
2
5
10
4
Obr. 27: Graf se záporně ohodnocenou hranou.
u u1 u2 u3 v
0 ∞ ∞ ∞ ∞
0 -3 ∞ 2 10
0 -3 3 1 10
0 -3 3 1 6
0 -3 3 1 6
v u u1 u2 u3
0 ∞ ∞ ∞ ∞
0 10 ∞ ∞ 5
0 7 9 ∞ 5
0 7 4 ∞ 5
0 7 4 10 5
Tabulka 1: Výpočet Dijkstrova algoritmu z různých počátečních vrcholů.
Řešení 8.8. Všechny neizomorfní grafy se čtyřmi vrcholy, viz obrázek.
31
8 GRAFY
Obr. 28: Celkem 11 neizomorfních grafů.
Řešení 8.9. Hledáme eulerovské grafy, přičemž postačující podmínkou je, aby
byl graf souvislý a všechny jeho vrcholy měly sudý stupeň, což dává možnosti
stupňů 0, 2 a 4. Vrchol(y) stupně 0 jsou ve sporu se souvislostí grafu, zůstávají
tedy kombinace stupňů 2 a 4. Jednoduchými úvahami zjistíme, že možnosti jsou
následující (až na izomorfismus):
2
2
2
2
2 2
4
2
2
2
2
4
4
2
2 4
4
4
4
4
Obr. 29: Neizomorfní eulerovské grafy s pěti vrcholy.
Řešení 8.10. Minimální kostru najdeme „hladovým“ algoritmem. Postupně přidáváme
hrany s nejnižším ohodnocením tak, aby přidáním hrany nevznikl cyklus.
Jedna z možných minimálních koster je na obrázku. Poznamenejme, že
2
3
2
3
3
3 1
1
1
2
Obr. 30: Jedna z možných minimálních koster.
minimálních koster je 3
2
2
1
2
1 = 12. Pro kontrolu si všechny minimální kostry
nakreslete.
Řešení 8.11.
a) Existuje celkem osm koster (bereme-li v úvahu izomorfismus dostaneme
však pouze dvě).
32
8 GRAFY
Obr. 31: Všechny kostry grafu.
b) Všimněme si, že minimální kostry grafu z podbodu b) vziknou přidáním
šestého vrcholu a příslušné hrany grafu z podbodu a). Existuje tedy opět
osm koster, avšak až pět různých (neizomorfních).
Obr. 32: Všechny kostry grafu.
Řešení 8.12. Poznamenejme, že když neexistuje vrchol s nejmenší aktuální vzdáleností
od daného vrcholu, tak nezáleží na tom, který z vrcholů majících minimální
vzdálenost, zvolíme. Výpočet je zaznamenán v tabulce na následující
straně.
33
8 GRAFY
u u1 u2 u3 u4 u5
0 ∞ ∞ ∞ ∞ ∞
0 ∞ ∞ 4 1 3
0 7 3 4 3
0 6 4 3
0 6 4
0 5
Tabulka 2: Dijsktrův algoritmus.
Řešení 8.13.
1) Uvedené grafy jsou izomorfní. Při následujícím značení je jeden z izomorfismů
dán takto: a → 3, b → 4, c → 5, d → 6, e → 1, f → 2.
a
b c
d
ef
1
2
3
4
5
6
2) Využijme pomocného tvrzení ze zadání. Zvolme H = {3}, na obrázku
vidíme, že indukované grafy P1, P2 nejsou izomorfní. (Pro přehlednost jsou
na obrázku zaznačené všechny vrcholy původních grafů. Indukované grafy
ovšem obsahují jen plné vrcholy.)
3) V izomorfních grafech jsou počty cyklů délky n stejné pro každé n ∈ N.
V druhém grafu jsou dva cykly délky 3 (viz obrázek), zatímco v prvním
grafu není cyklus délky 3 ani jeden. Proto zadané grafy nejsou izomorfní.
Obr. 33: Dva cykly délky 3.
34
8 GRAFY
4) Označme si vrcholy obou grafů (viz obrázek). První graf je zřejmě rovinný.
Přemístěním vrcholů 3 a 4 u druhého grafu vidíme, že i tento graf je rovinný.
Z konkrétního nakreslení je zřejmý izomorfismus grafů daný a → 1,
b → 3, c → 5, d → 2, e → 4.
e
a b
c
d
5
1 2
4
3
5
1
2
4
3
5) Uvedené grafy nejsou izomorfní, což ukážeme využitím stejného tvrzení
jako v případu 2). Nyní volíme H = {3}. První indukovaný podgraf je narozdíl
od toho druhého souvislý. (Pro přehlednost jsou na obrázku zaznačené
všechny vrcholy původních grafů. Indukované grafy ovšem obsahují
jen plné vrcholy.)
6) Uvedené grafy nejsou izomorfní, poněvadž první graf se skládá z dvou
komponent souvislosti (viz obrázek) a ten druhý je souvislý (existuje cesta
spojující všechny vrcholy, viz obrázek).
35