Předmluva
Cílem tohoto textu je stručně shrnout obsah předmětu Diskrétní matematika
přednášeného na PřF MU. Neměl by sloužit jako náhrada doporučené
literatury ani účasti na přednáškách, ale spíš jako určitá rozšířená osnova pro
opakování látky.
1 Logika
Logika se zabývá správným usuzováním a odvozováním závěrů. Budeme se
věnovat tzv. matematické logice, která se zaměřuje na vlasnosti matematických
objektů, odvozování výsledků a jejich dokazování.
K zápisu matematických skutečností se používá matematického jazyka.
Jeho výhodou je zestručnění a zpřesnění vyjadřování.
1.1 Výroková logika
Základním pojmem ve výrokové logice je výrok. Výrok může představovat
nějaké jednoduché tvrzení, které je pravdivé nebo nepravdivé. Z hlediska
logiky nás budou zajímat vztahy mezi výroky a posuzování pravdivosti tzv.
formulí, což jsou tvrzení složená z výroků.
Příklad 1. „Čtverec je čtyřúhelník a 2 je prvočíslo.“ je formule složená z
výroků „Čtverec je čtyřúhelník“ a „2 je prvočíslo.“ pomocí spojky „a“.
Z příkladu je zřejmé, že podobným způsobem bychom mohli vytvářet formule
z libovolných výroků a dokonce i z již vytvořených formulí. Má tedy
smysl zapomenout na konkrétní obsah výroků a pracovat s nimi jako s abstraktními
objekty. Nechť tedy písmena A, B, C, . . . značí výroky. Formule
budeme vytvářet postupným skládáním již vytvořených formulí pomocí tzv.
logických spojek. Používat budeme následující:
negace — čteme „ne“ nebo „neplatí“, značíme ¬,
konjunkce — čteme „a“, značíme ∧,
disjunkce — čteme „nebo“, značíme ∨,
implikace — čteme „jestliže . . . , potom . . . “ nebo „implikuje“, značíme →,
ekvivalence — čteme „právě když“ nebo „je ekvivalentní“, značíme ↔.
Definice formule (říká se jí induktivní) pak vypadá následovně:
1
Definice 1. (1) Každý výrok je formule.
(2) Jsou-li ϕ, ψ formule, pak (¬ϕ), (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ → ψ), (ϕ ↔ ψ)
jsou formule.
Chceme-li zjistit, zda je nějaký výraz korektně vytvořenou formulí, postupujeme
obráceně, tj. „rozebíráme“ výraz na jednodušší celky a kontrolujeme
zda jsou spojeny v souladu s pravidly definice. Uzávorkování uvnitř formule
je podstatné a může zcela změnit její smysl. Dohodněme se, že vnější závorku
lze vynechat a že negace má přednost před ostatními spojkami.
Příklad 2. Nechť A, B jsou výroky. (A∨B)∧¬A je formule vzniklá spojením
podformulí A ∨ B a ¬A. A ∨ B je spojením A a B a ¬A vznikla přidáním
negace k A. Jedná se tedy o korektně vytvořenou formuli.
Známe-li pravdivost podformulí, z nichž je formule vytvořena, vyhodnocuje
se pravdivost složené formule podle následující tabulky.
ϕ ψ ¬ϕ ϕ ∧ ψ ϕ ∨ ψ ϕ → ψ ϕ ↔ ψ
0 0 1 0 0 1 1
0 1 1 0 1 1 0
1 0 0 0 1 0 0
1 1 0 1 1 1 1
Zde 1 značí, že formule je pravdivá, a 0, že je nepravdivá. K posouzení
pravdivosti formule výrokové logiky tedy většinou potřebujeme znát pravdivost
výroků v ní obsažených a podle tabulky ji postupně dopočítáme. Můžeme
také dostat za úkol dopočítat pravdivost formule pro všechna možná
ohodnocení výroků, což obvykle řešíme sestrojením vhodné tabulky podfor-
mulí.
Je-li formule pravdivá pro libovolné ohodnocení výroků, nazývá se tautologie.
Je-li formule nepravdivá pro libovolné ohodnocení výroků, nazývá se
kontradikce.
Řekneme, že formule ϕ a ψ jsou ekvivalentní, pokud mají stejná pravdivostní
ohodnocení pro všechna ohodnocení výroků (tedy stejný sloupec
hodnot v pravdivostní tabulce), zapisujeme ϕ ⇔ ψ. Znamená to totéž jako
říct, že složená formule ϕ ↔ ψ je pravdivá. Zápis ϕ ⇔ ψ je tedy zkratkou
soudu vysloveného o dvou formulích, kdežto ϕ ↔ ψ je jediná formule. (Rozdílem
v zápisu se tedy nemusíme prozatím moc znepokojovat.) Ekvivalence
formulí znamená, že vyjadřují stejnou skutečnost, nikoli, že jsou si rovny (to
by musely mít totožný zápis).
Podobně řekneme, že z ϕ vyplývá ψ (neboli ψ je důsledkem ϕ, pokud pro
ψ je pravdivá vždy, když je pravdivá ϕ, značíme ϕ ⇒ ψ. Opět to znamená
totéž jako říct, že formule ϕ → ψ je pravdivá.
2
O tom, zda jsou dané formule ekvivalentní nebo jedna vyplývá z druhé, se
lze kromě sestrojení výrokové tabulky přesvědčit i úpravou podle logických
pravidel, což jsou jednoduché ekvivalence (nebo vyplývání) formulí. Tento
postup je obvyklý v matematických důkazech. Mezi užitečná pravidla patří:
¬¬ϕ ⇔ ϕ dvojí negace
ϕ ∧ ϕ ⇔ ϕ idempotence
ϕ ∨ ϕ ⇔ ϕ
ϕ ∧ ψ ⇔ ψ ∧ ϕ komutativita
ϕ ∨ ψ ⇔ ψ ∨ ϕ
(ϕ ∧ ψ) ∧ χ ⇔ ϕ ∧ (ψ ∧ χ) asociativita
(ϕ ∨ ψ) ∨ χ ⇔ ϕ ∨ (ψ ∨ χ)
ϕ ∧ (ψ ∨ χ) ⇔ (ϕ ∧ ψ) ∨ (ϕ ∧ χ) distributivita
ϕ ∨ (ψ ∧ χ) ⇔ (ϕ ∨ ψ) ∧ (ϕ ∨ χ)
ϕ ∧ (ϕ ∨ ψ) ⇔ ϕ absorpce
ϕ ∨ (ϕ ∧ ψ) ⇔ ϕ
ϕ ↔ ψ ⇔ (ϕ → ψ) ∧ (ψ → ϕ) odstranění ekvivalence
ϕ → ψ ⇔ ¬ϕ ∨ ψ odstranění implikace
¬(ϕ ∧ ψ) ⇔ ¬ϕ ∨ ¬ψ de Morganova pravidla
¬(ϕ ∨ ψ) ⇔ ¬ϕ ∧ ¬ψ
ϕ → ψ ⇔ ¬ψ → ¬ϕ obměna implikace
Z pravidel vyplývá zajímavý fakt, že každá formule je ekvivalentní formuli
tvořené pouze spojkami ¬, ∧, ∨ nebo i pouze ¬, ∧. Dokonce lze ekvivalentní
formuli sestrojit pomocí jediné speciální logické spojky (využití v elektro-
nice).
1.2 Predikátová logika
Prostředky výrokové logiky jsou poměrně slabé a k popisu většiny matematických
skutečností by nestačily. V predikátové logice se výroky nahrazují
tvrzeními popisujícími nějakou vlastnost objektů nebo vztahy mezi nimi,
např. x < 2 nebo x = y. K jazyku výrokové logiky přidáváme symboly proměnných
(např. x, y, z, . . . ) a tzv. predikátových symbolů (např. < , = , +, 0,
jejich přesnější vysvětlení prozatím odložíme). Krom toho máme k dispozici
kvantifikátory:
všeobecný — čteme „každý“, „všechny“, atp., značíme ∀,
3
existenční — čteme „existuje“ nebo „aspoň jeden“, značíme ∃.
Za kvantifikátorem musí vždy následovat proměnná, na kterou se kvantifikátor
vztahuje. Formule predikátové logiky se vytváří stejně jako ve výrokové
logice a navíc podle pravidla
(3) Je-li ϕ formule a x proměnná, jsou i (∀x)ϕ a (∃x)ϕ formule.
Příklad 3. (∀x)(∀y)(∃z)(x + z = y) je formule vzniklá postupným (trojím)
aplikováním pravidla (3) na formuli x + z = y.
Při posuzování pravdivosti formulí predikátové logiky je podstatné, v jaké
množině nebo struktuře se pohybujeme. Např. formule (∃x)(∀y)x ≤ y říká,
že existuje nejmenší prvek. V množině přirozených čísel N tedy platí, zatímco
v množině celých čísel Z neplatí. Proměnné ve formuli tedy zastupují prvky
množiny a predikátové symboly její strukturu (přesněji vysvětlíme v kapitole
Relace). Tautologií v predikátové logice rozumíme formuli platnou všude.
V predikátové logice máme k dispozici další logická pravidla pro práci s
kvantifikátory:
¬(∀x)ϕ ⇔ (∃x)¬ϕ negace kvantifikátoru
¬(∃x)ϕ ⇔ (∀x)¬ϕ
(∀x)(∀y)ϕ ⇔ (∀y)(∀x)ϕ komutativita kvantifikátorů
(∃x)(∃y)ϕ ⇔ (∃y)(∃x)ϕ stejného typu
(∃x)(∀y)ϕ ⇒ (∀y)(∃x)ϕ (jen v tomto směru!)
(∀x)(ϕ ∧ ψ) ⇔ (∀x)ϕ ∧ (∀x)ψ
(∃x)(ϕ ∨ ψ) ⇔ (∃x)ϕ ∨ (∃x)ψ
Pokud se proměnná x nevyskytuje ve ϕ, platí také
ϕ ∧ (∀x)ψ ⇔ (∀x)(ϕ ∧ ψ),
ϕ ∨ (∀x)ψ ⇔ (∀x)(ϕ ∨ ψ),
ϕ ∧ (∃x)ψ ⇔ (∃x)(ϕ ∧ ψ),
ϕ ∨ (∃x)ψ ⇔ (∃x)(ϕ ∨ ψ).
V predikátové logice se všechny proměnné a predikátové symboly vztahují
ke stejné množině. To může být někdy velmi omezující, proto se v matematice
používají i formule logik vyššího řádu, např. (∀x > 0)(∃n ∈ N)(0 < f(n) <
x).
4
2 Množiny
Veškeré matematické teorie (včetně logiky samotné) se dnes již budují axiomaticky,
tzn. stanoví se axiomy, což jsou určité formule, o kterých se předpokládá,
že pro objekty dané teorie vždy platí. Součástí logického systému jsou
dále odvozovací pravidla, pomocí kterých se dají dokazovat další formule.
Axiomaticky lze vybudovat i teorii množin, ale spokojíme se s „naivním“
přístupem a budeme předpokládat, že bezpečný způsob vytváření množin je
nám jasný.
Základním predikátovým symbolem teorie množin je ∈ označující náležení
prvku do množiny, např. x ∈ A značí, že x je prvkem množiny A. Tato
vlastnost je pouze relativní, tzn. i prvek nějaké množiny může být sám množinou
(případně obsahující jiné prvky). Pokud máme takovou složitější strukturu
množin a je zřejmá jejich hierarchie, obvykle značíme malým písmenem
a, b, c, . . . prvky v nejnižším „patře“, velkým písmenem A, B, C, . . . množiny,
které jsou jimi tvořeny a psacím velkým písmenem A, B, C, . . . množiny
vytvářené z předchozích množin. Pro snazší vyjadřování se posledně jmenovaným
také říká systémy množin.
Symbolem ∅ značíme prázdnou množinu, tj. množinu, která neobsahuje
žádný prvek. Množiny lze zapisovat výčtem, např. A = {x, y, z}, nebo specifikací
prvků nějakou vlastností, např. A = {x | x je celé liché číslo}. Dvě
množiny jsou si rovny, pokud mají stejné prvky, např. {a, b} = {b, a, a}
nebo {x | x je přirozené číslo menší než 4} = {1, 2, 3}. Formálně zapsáno
A = B ⇔ (x ∈ A ↔ x ∈ B).
Řekneme, že množina A je podmnožinou množiny B, pokud každý prvek
množiny A je i prvkem množiny B, značíme A ⊆ B. Vyjádřeno formulí,
x ∈ A → x ∈ B.
Věta 1. Nechť A, B, C jsou množiny. Pak platí:
(1) ∅ ⊆ A,
(2) A ⊆ A,
(3) (A ⊆ B ∧ B ⊆ C) → A ⊆ C,
(4) (A ⊆ B ∧ B ⊆ A) → A = B.
Důkaz. (1) U implikace x ∈ ∅ → x ∈ A není splněn předpoklad, tedy platí.
(2) x ∈ A → x ∈ A je tautologie.
(3) Pokud x ∈ A → x ∈ C by byla nepravdivá, pak x ∈ A je pravdivá a
x ∈ C pravdivá. Pak by ovšem neplatila x ∈ A → x ∈ B (pokud je x ∈ B
nepravdivá) nebo x ∈ B → x ∈ C (pokud je x ∈ B pravdivá). Tzn. neplatí-li
A ⊆ C, neplatí ani A ⊆ B ∧ B ⊆ A.
(4) Použijeme pravidlo pro odstranění ekvivalence: ((x ∈ A → x ∈ B) ∧
(x ∈ B → x ∈ A)) ⇔ (x ∈ A ↔ x ∈ B).
5
Definice 2. Nechť A, B jsou množiny.
Průnikem množin A, B se nazývá množina A∩B = {x | x ∈ A ∧ x ∈ B},
sjednocením množina A ∪ B = {x | x ∈ A ∨ x ∈ B}
a rozdílem množina A − B = {x | x ∈ A ∧ ¬x ∈ B}.
Je-li A ⊆ B, nazývá se množina B − A doplňkem množiny A v B a je-li
B známa, značí se doplněk A′
.
Potenční množinou množiny A se rozumí množina všech jejích podmnožin,
tj. množina P(A) = {B | B ⊆ A}.
Z vlastností logických operací ∧, ∨ snadno vyplývají obdobné vlastnosti
průniku a sjednocení:
A ∩ A = A, A ∪ A = A,
A ∩ B = B ∩ A, A ∪ B = B ∪ A,
(A ∩ B) ∩ C = A ∩ (B ∩ C), (A ∪ B) ∪ C = A ∪ (B ∪ C), atd.
Definice 3. Nechť A je systém množin. Definujeme
A = {x | (∀A ∈ A) x ∈ A},
A = {x | (∃A ∈ A) x ∈ A}.
Pro zpřehlednění systémů množin se často používá indexování. Znamená
to, že každá množina systému je označena ve tvaru Ai, kde i je pro každou
množinu jedinečný a nazývá se index. Množina všech indexů, řekněme I, se
nazývá indexová množina. Indexovat můžeme čímkoli, nejenom čísly. Systém
pak zapisujeme ve tvaru {Ai}i∈I a definici „velkého“ průniku a sjednocení
lze přepsat
i∈I
Ai = {x | (∀i ∈ I) x ∈ Ai},
i∈I
Ai = {x | (∃i ∈ I) x ∈ Ai}.
Uvědomme si, že A1 ∩ A2 = i∈{1,2} Ai, „velký“ průnik je tedy rozšířením
průniku dvou množin (podobně pro sjednocení). Platí např. i obecnější
distributivní zákony:
Věta 2. Nechť A je množina, {Bi}i∈I systém množin. Pak platí
A ∩
i∈I
Bi =
i∈I
(A ∩ Bi),
A ∪
i∈I
Bi =
i∈I
(A ∪ Bi).
6
Důkaz. x ∈ A ∩ i∈I Bi ⇔ x ∈ A ∧ x ∈ i∈I Bi ⇔ x ∈ A ∧ (∃i ∈ I) x ∈
Bi ⇔ (∃i ∈ I)(x ∈ A ∧ x ∈ Bi) ⇔ x ∈ i∈I(A ∩ Bi). Důkaz druhého
zákona je analogický.
Uspořádanou dvojici prvků a, b označme (a, b). Pro dvě uspořádané dvojice
(a, b), (c, d) platí (a, b) = (c, d), pokud a = c a b = d.
Definice 4. Nechť A, B jsou množiny. Kartézským součinem množin A, B
se nazývá množina
A × B = {(a, b) | a ∈ A ∧ b ∈ B}.
Kartézský součin není komutativní, ačkoli dvojice (a, b) z A×B a (b, a) z
B × A si vzájemně odpovídají (pořadí složek je důležité!). Dokonce není ani
asociativní — (A×B)×C má prvky tvaru ((a, b), c), zatímco A×(B×C) tvaru
(a, (b, c)). V praxi ale můžeme tento rozdíl zanedbávat a uvažovat součin
A × B × C jako množinu uspořádaných trojic (a, b, c).
Věta 3. Nechť A je množina, {Bi}i∈I systém množin. Pak platí
A ×
i∈I
Bi =
i∈I
(A × Bi),
A ×
i∈I
Bi =
i∈I
(A × Bi).
Důkaz. (a, b) ∈ A × i∈I Bi ⇔ a ∈ A ∧ b ∈ i∈I Bi ⇔ a ∈ A ∧ (∃i ∈
I) b ∈ Bi ⇔ (∃i ∈ I)(a ∈ A ∧ b ∈ Bi) ⇔ (∃i ∈ I) (a, b) ∈ A × Bi ⇔
(a, b) ∈ i∈I(A × Bi). Důkaz druhé rovnosti je analogický.
3 Zobrazení
Zobrazením množiny A do množiny B rozumíme předpis, který každému
prvku množiny A jednoznačně přiřazuje nějaký prvek množiny B. Zobrazení
f množiny A do B zapisujeme f : A → B. Množina A se nazývá definiční
obor, množina B obor hodnot. Skutečnost, že f zobrazí prvek a ∈ A na
prvek b ∈ B zapisujeme f(a) = b nebo a → b (pokud nehrozí záměna s
jiným zobrazním). Prvek a se nazývá vzor prvku b, prvek b se nazývá obraz
prvku a. Lze-li pomocí proměnné takto zadat celé zobrazení, říkáme výrazu
f(x) = . . . předpis zobrazení.
Příklad 4. (1) f : R → R, f(x) = x2
je zobrazení.
(2) f : R → R, f(x) =
√
x není zobrazení. Pro x < 0 není výraz
√
x
definován (přinejmenším není reálný).
7
(3) f : R+
→ R, f(x) =
√
x je zobrazení.
(4) f : Z → Z, f(x) = x
2
není zobrazení. Pro lichá x neleží obraz x
2
v oboru
hodnot.
Definice 5. Nechť f : A → B je zobrazení. f se nazývá
prosté (injektivní), jsou-li obrazy různých prvků různé, tj. f(a) = f(b) →
a = b,
na (surjektivní), má-li každý prvek oboru hodnot nějaký vzor, tj. (∀b ∈
B)(∃a ∈ A) f(a) = b,
bijektivní, je-li současně injektivní i surjektivní.
Příklad 5. (1) f : R → R, f(x) = x2
není injektivní ani surjektivní. Máme
(−1)2
= 12
, přitom −1 = 1. Např. prvek −1 nemá vzor.
(2) f : R → [−1; 1], f(x) = sin x je surjektivní, není injektivní. Každý prvek
má vzor (jeden z nich můžeme najít funkcí arcsin). Každý prvek intervalu
[−1; 1] má ovšem nekonečně mnoho vzorů (sin má periodu 2π).
(3) f : Z → Z, f(x) = 2x je injektivní, není surjektivní. Z 2x = 2y
vyplývá x = y. Jakékoli liché číslo nemá vzor.
(4) f : Z → Z, f(x) = −x je bijektivní. Z −x = −y plyne x = y a
libovolné x má vzor −x.
Mezi důležitá zobrazení patří:
identita — idA : A → A, x → x (bijekce),
inkluze — pro B ⊆ A předpis i : A → B, x → x (injekce),
prázdné zobrazení — oA : ∅ → A (injekce),
projekce — pA : A × B → A, pA((x, y)) = x, resp. pB : A × B →
B, pB((x, y)) = y (surjekce pro neprázdné A, B).
Nechť A, B, C jsou množiny a f : A → B, g : B → C zobrazení. Pak
existuje složené zobrazení g ◦ f : A → C definované předpisem
(g ◦ f)(x) = g(f(x)).
Věta 4. Nechť f : A → B, g : B → C, h : C → D jsou zobrazení mezi
množinami A, B, C, D. Pak platí:
(1) h ◦ (g ◦ f) = (h ◦ g) ◦ f,
(2) idB ◦ f = f,
(3) f ◦ idA = f.
8
Důkaz. (1) Pro libovolné x ∈ A platí (h ◦ (g ◦ f))(x) = h((g ◦ f)(x)) =
h(g(f(x))) = (h ◦ g)(f(x)) = ((h ◦ g) ◦ f)(x). Podobně (2) (idB ◦ f)(x) =
idB(f(x)) = f(x) a (3) (f ◦ idA)(x) = f(idA(x)) = f(x).
Věta 5. Nechť f : A → B, g : B → C jsou zobrazení mezi množinami
A, B, C. Pak platí:
(1) Jsou-li f, g injektivní, je i g ◦ f injektivní.
(2) Jsou-li f, g surjektivní, je i g ◦ f surjektivní.
(3) Je-li g ◦ f injektivní, je i f injektivní.
(4) Je-li g ◦ f surjektivní, je i g surjektivní.
Důkaz. Cvičení.
Zobrazení g : B → A se nazývá inverzní k zobrazení f : A → B, jestliže
g ◦ f = idA a f ◦ g = idB.
Věta 6. K zobrazení f : A → B existuje zobrazení inverzní právě tehdy, když
f je bijekce. Inverzní zobrazení je určeno jednoznačně.
Důkaz. Předpokládejme, že existuje zobrazení inverzní g : B → A. Pro x, y ∈
A máme f(x) = f(y) ⇒ x = (g ◦ f)(x) = (g ◦ f)(y) = y, tedy f je prosté.
Pro v ∈ B máme f(g(v)) = (f ◦ g)(v) = v, tedy g(v) je vzorem v a f je na.
Celkem f je bijekce.
Naopak předpokládejme, že f : A → B je bijekce. Každý prvek u ∈ V
má tedy nějaký vzor, protože f je na. Tento vzor je navíc jediný, protože f
je prosté. g : B → A tedy sestrojíme jako přiřazení jedinečných vzorů prvků
množiny B v zobrazení f.
Konečně předpokládejme, že g, h : B → A jsou dvě inverzní zobrazení k
zobrazení f : A → B. Pak g = g ◦idB = g ◦(f ◦h) = (g ◦f)◦h = idA ◦h = h.
Inverzní zobrazení k zobrazení f : A → B (už víme že jediné) budeme
značit f−1
: B → A.
Množinu všech zobrazení množiny A do množiny B značíme BA
.
Je-li B ⊆ A, definujeme její charakteristickou funkci χB : A → {0, 1}
předpisem
χB(x) =
1, x ∈ B,
0, x ∈ B.
Věta 7. Předpis B → χB určuje bijekci f : P(A) → {0, 1}A
.
Důkaz. Stačí najít inverzní zobrazení f−1
: {0, 1}A
→ P(A). Pro h ∈ {0, 1}A
položme f−1
(h) = {x ∈ A | h(x) = 1}. Zřejmě χf−1(h) = h a f−1
(χB) = B,
f−1
je tedy skutečně inverzní k f.
9
3.1 Mohutnost množiny
Řekneme, že množiny A, B mají stejnou mohutnost, pokud existuje bijekce
f : A → B. U konečných množin to znamená, že mají stejný počet prvků.
Z vlastností bijekcí vyplývá, že vztah „mít stejnou mohutnost“ je relací ekvivalence
na třídě všech množin (viz Relace). Každé množině pak můžeme korektně
přiřadit symbol reprezentující všechny množiny o stejné mohutnosti,
který nazýváme kardinální číslo. Pak říkáme, že množina A má příslušnou
mohutnost a zapisujeme ji |A|. Pro mohutnosti konečných množin se kardinální
čísla zapisují pomocí přirozených čísel a nuly (mohutnost prázdné
množiny) Např. píšeme |{a, b, c}| = 3.
Množina se nazývá spočetná, pokud má stejnou mohutnost jako množina
přirozených čísel. (Spočetná je tedy nekonečná!) Kardinální číslo spočetných
množin se značí symbolem ℵ0 (alef nula). Mezi spočetné množiny patří např.
N, N∪{0}, Z, N × N, Q a množina všech konečných posloupností přirozených
čísel.
Nekonečná množina, která není spočetná, se nazývá nespočetná. Mezi
nespočetné množiny patří např. R, P(N), NN
(tj. množina všech nekonečných
posloupností přirozených čísel). Uvedené příklady mají stejnou mohutnost,
která se nazývá mohutnost kontinua. Existují i množiny větších mohutností,
např. množina všech reálných funkcí (ovšem množina všech spojitých reálných
funkcí má ještě mohutnost kontinua).
4 Relace
Relace popisují vztahy mezi prvky množin. Podle počtu těchto množin rozlišujeme
relace na unární, binární, ternární, atd. Budeme se zabývat výhradně
binárními relacemi.
(Binární) relací R mezi množinami A, B je podmnožina R ⊆ A × B. Pokud
A = B, hovoříme o relaci na množině. Vztah (x, y) ∈ R také zapisujeme
xRy.
Pro znázornění relací se někdy používají šipkové diagramy, kde příslušnost
dvojice (x, y) do relace se zakresluje jako šipka z x do y. U relací na množině
je možný dvojí způsob kreslení diagramů — jedna kopie množiny a šipky
uvnitř (obvyklé) nebo dvě kopie množiny a šipky mezi nimi (vhodnější pro
skládání relací).
Příklad 6. (1) Nechť A je množina knih v knihovně, B množina čtenářů.
Relaci R můžeme definovat jako množinu výpůjček, tj. R = {(x, y) ∈ A×B |
čtenář y má půjčenou knihu x}.
(2) < je relace na množině N.
10
(3) = je relace na jakékoli množině (tzv. identická relace, viz dále).
(4) ⊆ je relace na P(A) pro jakoukoli množinu A.
(5) Zobrazení f : A → B je relace mezi A a B splňující podmínku (∀x ∈
A)(∃!y ∈ B)(x, y) ∈ f (∃! znamená „existuje právě jedno“). Takto se správně
zavádí pojem zobrazení.
Skládání relací rozšiřuje skládání zobrazení a pro relace R ⊆ A × B, S ⊆
B × C je definováno následovně:
S ◦ R = {(x, y) ∈ A × C | (∃z ∈ B)((x, z) ∈ R ∧ (z, y) ∈ S)}.
Identická relace idA na množině A je totožná s identickým zobrazením
na A chápaným jako relace, tj. idA = {(x, x) | x ∈ A}.
Inverzní relace R−1
⊆ B × A k relaci R ⊆ A × B je relace R−1
=
{(y, x) | (x, y) ∈ R}. Všimněte si, že inverzi má každá relace. Pokud R
je zobrazení, které není bijektivní, R−1
není zobrazení (proto se inverzní
zobrazení definovalo jen pro bijekce). Také obecně R◦R−1
= idB a R−1
◦R =
idA.
Věta 8. Nechť R ⊆ A × B, S ⊆ B × C, T ⊆ C × D jsou relace. Pak platí:
(1) (T ◦ S) ◦ R = T ◦ (S ◦ R),
(2) R ◦ idA = R,
(3) idB ◦ R = R.
Důkaz. (1) (T ◦ S) ◦ R = {(x, y) ∈ A × D | (∃z ∈ B)((x, z) ∈ R ∧ (z, y) ∈
T ◦ S)} = {(x, y) ∈ A × D | (∃z ∈ B)((x, z) ∈ R ∧ (∃w ∈ C)((z, w) ∈
S ∧ (w, y) ∈ T))} = {(x, y) ∈ A×D | (∃z ∈ B, w ∈ C)((x, z) ∈ R ∧ (z, w) ∈
S ∧ (w, y) ∈ T)}. Pravá strana rovnosti se analogicky upraví na stejný tvar.
(2) R ◦ idA = {(x, y) | (∃z ∈ A)((x, z) ∈ idA ∧ (z, y) ∈ R)}, přitom
(x, z) ∈ idA nastává jen pro x = z, odtud R ◦ idA = R. Podobně (3).
Relace ρ na množině A se nazývá
reflexivní — (∀x)(xρx, tj. idA ⊆ ρ,
symetrická — (∀x, y)(xρy → yρx), tj. ρ = ρ−1
,
antisymetrická — (∀x, y)((xρy ∧ yρx) → x = y), tj. ρ ∩ ρ−1
⊆ idA,
tranzitivní — (∀x, y, z)((xρy ∧ yρz) → xρz), tj. ρ ◦ ρ ⊆ ρ.
ekvivalence, je-li reflexivní, symetrická a tranzitivní,
uspořádání, je-li reflexivní, antisymetrická a tranzitivní.
11
Vlastnosti symetrie a antisymetrie nejsou protikladné — lze najít relace,
které splňují obě, a relace, které nesplňují žádnou.
Příklad 7. (1) < na N je antisymetrická a tranzitivní, není relexivní ani
symetrická.
(2) ⊆ na P(A) je relace uspořádání.
(3) Relace {(x, x + 1) | x ∈ N} na N je antisymetrická, není reflexivní,
symetrická ani tranzitivní.
(4) Identická relace splňuje všechny čtyři vlastnosti, je tedy současně relací
ekvivalence i uspořádáním. (Je to jediná taková relace na dané množině.)
4.1 Relace ekvivalence a rozklady
Rozkladem množiny A se nazývá systém podmnožin R ⊆ P(A) splňující:
(1) R = A (systém pokrývá množinu),
(2) (∀B, C ∈ R)(B = C → B ∩ C = ∅) (množiny jsou po dvou
disjunktní).
Prvky rozkladu se nazývají třídy rozkladu. Z definice je zřejmé, že každý
prvek množiny A patří do právě jedné třídy rozkladu, pro prvek x ji značíme
[x]. Prvek x se také nazývá reprezentantem třídy [x]. Zobrazení p :
A → R, p(x) = [x] přiřazující každému prvku třídu, ve které leží, se nazývá
projekce (neplést s projekcemi kartézského součinu).
Věta 9. Nechť R je rozklad množiny A. Pak předpis xρRy ⇔ [x] = [y]
definuje relaci ekvivalence na A.
Naopak, je-li ρ relace ekvivalence na A, pak systém Rρ = {{y | yρx} |
x ∈ A} je rozklad množiny A.
Přiřazení R → ρR, ρ → Rρ určují bijektivní korespondenci mezi množinou
všech rozkladů a množinou všech relací ekvivalence na množině A.
Důkaz. Reflexivita, symetrie a tranzitivita relace ρR snadno vyplývá z definice
relace a vlastností rovnosti.
Relace ekvivalence je reflexivní, proto x ∈ {y | yρx} pro každé x ∈ A, a
tedy systém Rρ pokrývá A. Zvolme x, y ∈ A, B = {z | zρx}, C = {z | zρy}
a předpokládejme, že w ∈ B ∩ C. Tedy wρx a ze symetrie také xρw. Pro
z ∈ A platí zρx a z tranzitivity dostáváme zρw. Naopak, pokud zρw, pak
z tranzitivity dostaneme zρx, čili z ∈ B. Celkem máme z ∈ B ⇔ zρw a
podobně odvodíme, že z ∈ C ⇔ zρw. Odtud B = C, tedy prvky systému
R jsou po dvou disjunktní.
Potřebujeme ukázat, že složení R → ρR → RρR
vrací původní rozklad
a ρ → Rρ → ρRρ původní relaci ekvivalence. Platí T ∈ R ⇔ T = {y |
[x] = [y]} ⇔ T = {y | xρRy} ⇔ T ∈ RρR
a s využitím úvah z předešlého
odstavce také xρy ⇔ {z | zρx} = {z | zρy} ⇔ [x]Rρ = [y]Rρ ⇔ xρRρ y.
12
Rozklad příslušný relaci ekvivalence ρ na množině A značíme A/ρ a někdy
nazýváme faktorizací množiny A nebo faktormnožinou.
Jádro zobrazení f : A → B je relace ekvivalence Jf na množině A daná
podmínkou x Jf y ⇔ f(x) = f(y).
Věta 10. Každá relace ekvivalence je jádrem své projekce.
Důkaz. Plyne přímo z definice.
4.2 Uspořádané množiny
Uspořádanou množinou rozumíme množinu s pevně zvoleným uspořádáním.
Nechť (A, ≤) je uspořádaná množina. Pokud x ≤ y nebo y ≤ x, říkáme, že
x, y jsou porovnatelné (srovnatelné), v opačném případě jsou neporovnatelné
(nesrovnatelné). (A, ≤) se nazývá lineárně uspořádaná (řetězec), pokud jsou
každé dva prvky srovnatelné. (A, ≤) se nazývá protiřetězec, pokud jsou každé
dva prvky nesrovnatelné.
Říkáme, že prvek x pokrývá y nebo že y je následníkem x pokud y ≤
x, y = x a (∀z)(y ≤ z ≤ x → (z = y ∨ z = x)). Hasseovský diagram je
znázornění uspořádané množiny, kde pro každou dvojici prvků x ≤ y je x
nakreslen níž než y a dva prvky jsou spojeny čarou, pokud jeden pokrývá
druhý. Jiné prvky nesmí být spojeny (zejména neporovnatelné)! Chápeme-li
následníka jako relaci na A, lze původní uspořádání ≤ snadno zrekonstruovat
jako její reflexivní a tranzitivní obal. Hasseovský diagram tedy jednoznačně
(a velmi úsporně) určuje uspořádání.
Věta 11. Je-li ≤ relace uspořádání na množině A, pak ≤−1
je také relace
uspořádání.
Důkaz. Přímočarý.
Důsledkem věty je tzv. princip duality. Funguje tak, že každé tvrzení týkající
se např. největšího prvku lze přeformulovat na analogické týkající se
nejmenšího prvku (protože v duálním uspořádání se stane prvkem největším
a lze na něj aplikovat původní tvrzení). Hasseovský diagram duálního
uspořádání vznikne otočením původního „hlavou dolů“.
Prvek x se nazývá
největší — pokud (∀y)(y ≤ x),
nejmenší — pokud (∀y)(x ≤ y),
maximální — pokud (∀y)(x ≤ y → x = y),
minimální — pokud (∀y)(y ≤ x → x = y).
13
Věta 12. Největší prvek je maximální a to jediný.
Důkaz. Nechť x je největší a předpokládejme x ≤ y. Protože x je největší,
platí y ≤ x. Z antisymetrie dostáváme x = y, tedy x je maximální. Předpokládejme,
že x′
je také maximální. Pak x′
≤ x, protože x je největší. Potom
ovšem x′
= x, protože x′
je maximální.
Z principu duality dostáváme, že nejmenší prvek je jediný minimální.
Z věty současně vyplývá, že uspořádaná množina může mít nejvýše jeden
největší a nejvýše jeden nejmenší prvek. Maximálních a minimálních prvků
může být víc, např. v protiřetězci to jsou všechny prvky. Není pravda, že
jediný maximální prvek musí být největší.
Prvek x se nazývá horní závorou podmnožiny B ⊆ A, pokud (∀y ∈
B)(y ≤ x). x se nazývá dolní závorou B, pokud (∀y ∈ B)(x ≤ y). Množinu
horních (resp. dolních) závor množiny B označme HZ(B) (DZ(B)).
Nejmenší prvek množiny HZ(B) nazýváme supremum množiny B, největší
prvek množiny DZ(B) nazýváme infimum množiny B.
Horní závorou celé množiny A může být jen její největší prvek. Horní
závorou prázdné množiny je libovolný prvek množiny A, supremem prázdné
množiny je tedy nejmenší prvek. Supremum (nějaké množiny) nemusí existovat
ani v případě, že množina horních závor je neprázdná.
Uspořádaná množina se nazývá úplný svaz, pokud každá její podmnožina
má supremum i infimum (také říkáme, že má všechna suprema a infima).
Věta 13. Má-li uspořádaná množina (A, ≤) všechna suprema, má i všechna
infima.
Důkaz. Nechť B ⊆ A je libovolná. Protože A má nejmenší prvek, bude (přinejmenším)
tento prvek dolní závorou B, tedy množina C = DZ(B) je neprázdná.
Nechť x je supremum C. Každý prvek y ∈ B je současně horní
závorou C, proto x ≤ y (jakožto supremum je x nejmenší horní závorou C).
Odtud dostáváme, že x je také dolní závorou B. Protože je největší, jedná se
o infimum množiny B.
Příklad 8. 1) (N, ≤) není úplný svaz, protože nemá největší prvek. Mohlo
by se zdát, že má všechna infima (a tudíž i všechna suprema), ale ta mají jen
neprázdné podmnožiny. (Největší prvek jakožto inf ∅ neexistuje.) Suprema
existují právě pro konečné podmnožiny.
2) (P(A), ⊆) je úplný svaz pro libovolnou množinu A. Suprema jsou sjednocení
systémů množin, infima průniky (s výjimkou infima prázdné množiny).
3) Reálný uzavřený interval ([0; 1], ≤) je úplný svaz.
4) Racionální uzavřený interval ([0; 1] ∩ Q, ≤) není úplný svaz. Má sice
největší i nejmenší prvek, ale např. množina [0;
√
2
2
) ∩ Q nemá supremum (v
R by to bylo
√
2
2
, které ovšem není racionální).
14
Nechť (A, ≤), (B, ) jsou uspořádané množiny. Zobrazení f : A → B se
nazývá izotonní, pokud (∀x, y ∈ A)(x ≤ y → f(x) f(y)). f se nazývá
izomorfismus, pokud je bijektivní a platí (∀x, y ∈ A)(x ≤ y ↔ f(x) f(y)).
(Ekvivalentně lze izomorfismus definovat jako bijektivní izotonní zobrazení,
k němuž je zobrazení inverzní také izotonní). Trochu zjednodušeně se dá říct,
že izomorfní uspořádané množiny mají stejný hasseovský diagram.
Příklad 9. (1) Konstantní zobrazení f(x) = k pro pevně zvolené k ∈ B je
vždy izotonní.
(2) Posunutí f : (N, ≤) → (N, ≤), f(n) = n + 1 je izotonní a splňuje
podmínku dokonce jako ekvivalenci. Není ovšem izomorfismem, protože není
bijektivní.
(3) Nechť ({a, b}, =) je dvouprvkový protiřetězec a ({1, 2}, ≤) dvouprvkový
řetězec. Zobrazení a → 1, b → 2 je izotonní, jeho inverze izotonní není.
5 Kombinatorika
5.1 Permutace
Permutace udávají počet pořadí prvků n-prvkové množiny, neboli počet bijekcí
na sebe (těm se také říká permutace). Pro první prvek můžeme vybrat
z n možných obrazů, pro druhý už jen n − 1, atd., na poslední n-tý prvek
zbyde jediný použitelný obraz. Celkový počet je tedy n!.
5.2 Variace
Variace udávají počet uspořádaných výběrů (tj. posloupností) k neopakujících
se prvků z n-prvkové množiny, neboli počet injektivních zobrazení kprvkové
množiny do n- prvkové. Odvozují se podobně jako permutace, ale
posledním prvkem je k-tý, kterému odpovídá n − k + 1 možných obrazů. Výsledný
součin n(n − 1) . . .(n − k + 1) lze formálně rozšířit zlomkem (n−k)!
(n−k)!
a
upravit na tvar n!
(n−k)!
.
5.3 Kombinace
Kombinace udávají počet neuspořádaných výběrů k prvků z n-prvkové množiny,
neboli počet k-prvkových podmnožin. Uvážíme-li všechny uspořádané
výběry odpovídající jisté k-prvkové podmnožině, bude jich vždy tolik, kolik
je všech permutací těchto k prvků, tedy k!. Tento počet je stejný pro
všechny k-prvkové podmnožiny, můžeme tedy celkový počet uspořádaných
15
výběrů (variace) vydělit k! a dostaneme výsledek n!
k!(n−k)!
. Toto číslo se nazývá
kombinační a značí (n
k ).
Věta 14. Nechť n, k ∈ N0, k ≤ n. Pak platí
(1) (n
0 ) = 1, (n
1 ) = n,
(2) (n
k ) = (n
n−k),
(3) (n
k ) + (n
k+1) = (n+1
k+1).
Důkaz. (1) Zřejmé.
(2) Mezi podmnožinami dané množiny a jejími doplňky existuje zřejmá
bijekce. Počet k-prvkových podmnožin tedy bude stejný jako počet jejich
(n−k)-prvkových doplňků. Rovnost také vyplývá ze symetrie výrazu n!
k!(n−k)!
vzhledem ke k a n − k.
(3) Máme-li z n+1-prvkové množiny A vybrat k +1 prvků, lze to provést
rovněž tak, že v ní zvolíme jeden význačný prvek x. k + 1-prvkové podmnožiny
pak můžeme rozlišit podle toho, zda x obsahují nebo ne. Ty, které ho
neobsahují, vznikly jako podmnožiny n-prvkového zbytku A − {x} a je jich
tedy (n
k+1). Do podmnožin, které x obsahují, se vybíralo z A − {x} zbylých
k prvků, je jich tedy (n
k ). Vlastnost „náležení prvku x“ zřejmě zaručuje, že
vzniklé systémy podmnožin jsou disjunktní a celkový počet podmnožin tedy
získáme jako součet počtů jejich prvků. Důkaz lze rovněž provést algebraickou
úpravou výrazů dosazených za kombinační čísla.
Věta 15. (binomická) Nechť x, y ∈ R − 0, n ∈ N. Pak platí
(x + y)n
=
n
i=0
(n
i )xi
yn−i
.
Důkaz. Důkaz lze provést např. indukcí vzhledem k n s využitím vztahů
z předchozí věty. Jednodušší je však přímá kombinatorická úvaha. Výraz
(x+y)n
odpovídá součinu n závorek (x+y). Jejich roznásobením dostaneme
výrazy tvaru xi
yn−i
, protože z každé závorky vybereme buďto x nebo y a
součet exponentů tedy musí být n. Pro dané i bude výrazů celkem (n
i ), protože
právě toto číslo odpovídá počtu (neuspořádaných) výběrů těch závorek, ze
kterých se použije x (z ostatních se použije y).
5.4 Permutace s opakováním
Uvažujme n-prvkovou množinu a na ní relaci ekvivalence. Ekvivalenci interpretujeme
jako nerozlišitelnost prvků (např. stejné obarvení). Permutace s
opakováním udávají počet pořadí prvků dané množiny, přičemž pořadí lišící
se pouze ekvivalentními prvky považujeme za stejná. (Přesněji bychom
16
takto zavedli ekvivalenci pořadí a pak by se jednalo o počet tříd příslušného
rozkladu množiny všech pořadí.) Každé pořadí n prvků zřejmě určuje pořadí
prvků v každé třídě, vzájemně ekvivalentních (tj. zaměnitelných) pořadí
tedy bude v každé třídě n1!n2! . . . nk!, kde ni jsou počty prvků v jednotlivých
třídách (platí tedy n1 + · · · + nk = n). Tímto číslem vydělíme celkový počet
pořadí a dostaneme výsledek
n!
n1!n2! . . .nk!
.
Permutace (bez opakování) jsou vlastně zvláštním případem permutací s
opakováním, kde relací ekvivalence je identita.
5.5 Variace s opakováním
Variace s opakováním odpovídají uspořádaným výběrům k prvků z n-prvkové
množiny, kde každý prvek může být vybírán opakovaně. Situace přesně odpovídá
počtu zobrazení k-prvkové do n-prvkové (pro každý z k prvků vybíráme
jeho obraz). Protože pro každou pozici (prvek) máme na výběr n možností
(nezávisle na ostatních), bude celkový počet nk
.
Pozor, variace s opakováním nepředstavují zobecnění variací bez opakování
ani permutací s opakováním.
5.6 Kombinace s opakováním
Kombinace s opakováním udávají počet rozdělení n nerozlišitelných prvků do
k (rozlišitelných) přihrádek. Úloha se řeší tak, že k přihrádek znázorníme jako
řadu rozdělenou k − 1 oddělovači, mezi které vkládáme n prvků. Dostaneme
tak řadu n + k − 1 „prvkooddělovačů“ a výsledek určíme jako permutace s
opakováním, kde rozklad sestává ze dvou tříd — třídy prvků a třídy oddělovačů.
Rovněž můžeme uvažovat tak, že z n + k − 1-prvkové řady určíme n
prvků (nebo k − 1 oddělovačů), což provedeme jako neuspořádaný výběr, tj.
kombinace. V každém případě dojdeme k výsledku (n+k−1
n ).
5.7 Princip inkluze a exkluze
Principu se užívá v úlohách, kde prvky mohou mít nějaké vlastnosti A1, . . . , An
a potřebujeme určit počet prvků které buďto mají alespoň jednu z těchto
vlastností nebo naopak žádnou. Relaci „mít vlastnost Ai“ můžeme interpretovat
také jako příslušnost prvku do množiny Ai a jedná se pak o určení počtu
prvků sjednocení n
i=1, resp. jeho doplňku. Nutným předpokladem k vyřešení
17
úlohy je znalost počtu prvků libovolných průniků množin Ai včetně množin
samotných (a případně celé nosné množiny, ve které se úloha odehrává).
Princip inkluze a exkluze funguje na principu zpřesňování odhadu. Počet
prvků sjednocení nejprve odhadneme jako součet počtu prvků jednotlivých
množin. Prvky, které se nachází v průniku dvou množin, byly však
započítány dvakrát, a proto je následně odečteme jako počty prvků průniků
dvouprvkových podsystémů. Tento odhad ovšem nebude fungovat pro prvky
nacházející se v průniku tří množin — ty byly započítány třikrát v prvním
odhadu a odečteny třikrát ve druhém, musíme je tedy zase přičíst. Takto se
postupně dopracujeme až k průniku celého systému podmnožin, kde teprve
dostaneme přesný výsledek.
Věta 16. Nechť M je konečná množina a {Ai}i∈I systém jejích navzájem
různých podmnožin. Pak platí
M −
i∈I
Ai =
J⊆I
(−1)|J|
j∈J
Aj
(pro J = ∅ klademe ∅ = M).
Důkaz. Uvažujme libovolný prvek x ∈ i∈I Ai. Nechť K ⊆ I je množina těch
indexů i, že x ∈ Ai. Víme, že K = ∅ a x se objeví v j∈J Aj právě tehdy,
když J ⊆ K. Množina K má přitom (
|K|
j ) j-prvkových podmnožin, celkový
příspěvěk prvku x do součtu na pravé straně tedy bude |K|
j=0(−1)j
(
|K|
j ), což
je podle binomické věty rovno (1 − 1)|K|
= 0.
Naproti tomu prvek x ∈ M − i∈I Ai se na pravé straně objeví pouze
ve výrazu M = ∅, který má kladné znaménko a do součtu tedy x přispěje
hodnotou 1.
Pro počet prvků sjednocení pak odečtením dostáváme formuli
i∈I
Ai =
∅=J⊆I
(−1)|J|+1
j∈J
Aj .
Příklad 10. (1) Pro tříprvkový systém A1, A2, A3 vypadá princip inkluze a
exkluze po rozepsání následovně: |A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩
A2| − |A1 ∩ A3| − |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|.
(2) (úloha o šatnářce) Zapomětlivá šatnářka vydá n pánům zcela nahodile
n klobouků. Určete pravděpodobnost situace, že žádný pán nedostane svůj
klobouk.
Řešení: Celkový počet vydání klobouků je n!. Situace, že některý pán dostane
svůj klobouk odhadneme číslem (n
1 )(n − 1)!, kde (n
1 ) je počet výběrů
18
příslušného pána a (n−1)! je počet rozdělení zbylých klobouků. Dále odhadneme
číslem (n
2 )(n−2)! počet situací, kdy dva pánové dostanou své klobouky,
atd. Celkem dostaneme řadu
n! − (n
1 )(n − 1)! + (n
2 )(n − 2)! − · · · + (−1)n
=
n
i=0
(−1)i
(n
i )(n − i)!
a pravděpodobnost určíme jako podíl k celkovému počtu vydání n!. Pro n →
∞ pravděpodobnost konverguje k číslu 1
e
.
(3) Určete počet surjektivních zobrazení k-prvkové množiny na n-prvkovou.
Řešení: Počet všech zobrazení je nk
. Budeme postupně odhadovat počty
zobrazení, kde jeden, dva, atd. z n prvků oboru hodnot nejsou využity, tj.
nezabrazuje se na ně žádný prvek z definičního oboru. Užitím principu inkluze
a exkluze dojdeme k řadě
nk
− (n
1 )(n − 1)k
+ (n
2 )(n − 2)k
− · · · + (−1)(n−1)
( n
n−1)1k
=
n−1
i=0
(−1)i
(n
i )(n − i)k
.
6 Grafy
6.1 Základní pojmy
(Obyčejným neorientovaným) grafem rozumíme dvojici G = (V, E), kde V
je konečná množina vrcholů, E množina hran a platí E ⊆ (V
2 ), tj. E je
podmnožina množiny všech dvojprvkových podmnožin množiny V . O hraně
e = {u, v} říkáme, že spojuje vrcholy u, v. Existuje-li pro vrcholy u, v spojující
hrana, tj. {u, v} ∈ E, říkáme také, že vrcholy spolu sousedí.
Orientovaným grafem rozumíme dvojici G = (V, E), kde E je relace na
V . Hranami jsou tedy uspořádané dvojice vrcholů, navíc mohou existovat
smyčky na stejném vrcholu. Obyčejný graf lze chápat jako orientovaný, kde
relace definující hrany je symetrická a ireflexivní (tj. (∀x)(x, x) ∈ E).
Lze definovat orientované grafy bez smyček nebo obyčejné se smyčkami,
ale to nebudeme potřebovat. Rovněž se lze setkat s pojmem multigrafu, kde
mezi dvěma vrcholy může existovat více hran (případně více stejně orientovaných
hran u orientovaných grafů).
Grafy lze reprezentovat graficky, tj. každému vrcholu je (injektivně) přiřazen
bod v rovině a každé hraně křivka s příslušnými koncovými body. Přitom
křivka nesmí procházet žádným dalším vrcholem. Jelikož orientovaný (a potažmo
i neorientovaný) graf je definován jako relace, lze ho reprezentovat
19
jako binární čtvercovou matici E = (euv), kde
euv =
1, (u, v) ∈ E,
0, (u, v) ∈ E.
Další možností je reprezentace grafu seznamem sousedů, kde každému vrcholu
je přiřazena posloupnost všech jeho sousedů. Každý z uvedených způsobů
reprezentace lze zobecnit i na multigrafy (rozmyslete si).
Uvažujme nyní obyčejný graf G = (V, E). Sledem se nazývá posloupnost
vrcholů (v1, v2, . . . , vn) taková, že (∀1 ≤ i ≤ n − 1){vi, vi + 1} ∈ E (tj. dva
následující vrcholy sledu jsou sousední). Cestou se rozumí sled, v němž se
žádný vrchol neopakuje. Uzavřeným sledem rozumíme sled, v němž v1 = vn.
Kružnicí se nazývá uzavřený sled, kde se neopakuje žádná hrana ani žádný
vrchol s výjimkou prvního a posledního. Kružnice lišící se pouze počátečním
vrcholem sledu se obvykle nerozlišují. U orientovaného grafu má smysl u
definice sledu a cesty zohlednit orientaci hran. Délkou sledu/cesty/kružnice
se nazývá počet zúčastněných hran.
Podgraf grafu G = (V, E) je dvojice množin G′
= (V ′
, E′
) splňující V ′
⊆
V a E′
⊆ E ∩(V ′
2 ). Pokud E′
= E ∩(V ′
2 ), nazývá se podgraf úplný. (V definici
podgrafu orientovaného grafu (V ′
2 ) nahradíme V ′
× V ′
.) Je-li G′
podgrafem
G, říkáme také, že G obsahuje G′
.
Graf se nazývá souvislý, pokud mezi libovolnými dvěma vrcholy existuje
cesta. (Mohli bychom místo cest uvažovat pouze sledy, ovšem z každého
sledu lze vypustit každý uzavřený sled mezi dvěma výskyty téhož prvku,
čímž nakonec dostaneme cestu.) Každý maximální úplný souvislý podgraf se
nazývá komponentou grafu.
Počet sousedů vrcholu v nazýváme stupněm a značíme st(v). Kružnici
můžeme alternativně definovat jako souvislý podgraf, v němž má každý vrchol
stupeň 2.
Graf neobsahující kružnici se nazývá les. Souvislý les se nazývá strom.
Maximální podgraf souvislého grafu, který je stromem, nazýváme kostra.
Věta 17. (1) Počet hran stromu je o 1 menší než počet jeho vrcholů. Naopak
každý souvislý graf s touto vlastností je strom.
(2) Každá kostra obsahuje všechny vrcholy.
Důkaz. (1) Dokážeme indukcí. Pro |V | = 1 je |E| = 0 a tvrzení platí.
Stačí dokázat, že strom s alespoň dvěma vrcholy obsahuje aspoň jeden
vrchol stupně jedna. Žádná z cest spojující jiné dva vrcholy ho neobsahuje,
proto jeho odstraněním spolu s příslušnou hranou dosteneme podle indukčního
předpokladu souvislý podgraf vyhovující podmínce a tedy strom. Předpokládejme
sporem, že stupeň každého vrcholu je alespoň 2. To umožňuje se-
20
strojit sled libovolné délky, ve kterém jsou dvě následující hrany různé. S ohledem
na konečnost grafu se časem musí některý vrchol zopakovat. Uvážíme-li
posloupnost mezi některými nejbližšími výskyty vrcholu, dostaneme kružnici,
což je spor.
Přidáváme-li naopak ke stromu nový vrchol a novou hranu, aby vzniklý
graf byl souvislý, lze to provést pouze tak, že nová hrana připojí nový vrchol
k některému původnímu vrcholu. Pak bude mít nový vrchol stupeň 1 a
nevznikne tak kružnice.
(2) Předpokládejme, že kostra neobsahuje vrchol v. Protože graf je souvislý,
existuje cesta (v, v1, v2, . . ., vn) do některého vrcholu kostry. Zvolme i
nejmenší takové, že vi je už kosterní vrchol. Přidáním hran {v, v1}, {v1, v2}, . . . , {vi−1, vi}
ke kostře dostaneme souvislý graf bez kružnic (žádný z vrcholů (v, v1, v2, . . ., vi−1)
v kostře není a jedná se o cestu), což je spor s maximalitou kostry.
Ohodnocením grafu (také vahou) se nazývá zobrazení w : E → R. Ohodnocení
lze rozšířit na cesty, kružnice, kostry atd., když položíme w(K) =
e∈K w(e). Mezi důležité problémy teorie grafů patří nalezení minimální
cesty a nalezení minimální kostry. (Minimalita je nyní míněna vzhledem k
ohodnocení.)
6.2 Minimální cesta
Problém minimální cesty lze řešit u orientovaného i neorientovaného grafu.
Většina algoritmů používá pomocné ohodnocení vrcholů δ : V → R, které
představuje nejlepší průběžnou hodnotu cesty do daného vrcholu. Úprava
ohodnocení se provadí prostřednictvím tzv. relaxace hran, kdy původní hodnotu
δ(v) nahrazujeme součtem δ(u) + w(u, v), pokud je menší. Znamená to,
že jsme nalezli výhodnější cestu do vrcholu v přes hranu (u, v).
Je-li ohodnocení grafu nezáporné, můžeme minimální cestu z vrcholu u
do vrcholu v najít pomocí Dijkstrova algoritmu. V něm se na začátku nastaví
δ(u) := 0, δ(x) := ∞ pro x = u a A := V (inicializace). V každém kroku
algoritmu se z množiny A vybere vrchol x s nejmenším δ(x) a provedou se
relaxace hran do sousedních vrcholů. (Je-li takových vrcholů víc, lze zvolit
libovolný.) Následně se x vyřadí z množiny A a průchod cyklem se opakuje.
Hodnota δ(x) vybraného vrcholu je už výslednou hodnotou minimální cesty
z u do x. Není nutné relaxovat hrany vedoucí do již vyřazených vrcholů,
protože jejich δ není větší (byly vybrány dříve) a s ohledem na nezápornost
ohodnocení by relaxace nic nepřinesla. Algoritmus končí návštěvou posledního
vrcholu, po níž je A = ∅.
Předpoklad nezápornosti ohodnocení je důležitý, jinak může dojít k situaci,
že vrchol je vyhodnocen a vyřazen dřív, než se relaxuje některá záporně
21
ohodnocená hrana ležící na minimální cestě.
Dijkstrův algoritmus jako vedlejší produkt počítá i minimální cesty do
všech ostatních vrcholů. Hrana použitelná do minimální cesty splňuje rovnost
δ(x) + w(x, y) = δ(y) (i u neorientovaného grafu je pak důležité, kterým
směrem je rovnost splněna!).
6.3 Minimální kostra
Pro hledání minimální kostry si uvedeme tři algoritmy: Kruskalův (hladový),
Jarníkův (Primův) a Borůvkův. Problém budeme řešit pro neorientovaný
graf.
Kruskalův algorimus začíná s množinou hran F := E a průběžnou kostrou
K := ∅. V každém průchodu vybere z F hranu e s nejmenším ohodnocením.
Pokud K ∪ {e} neobsahuje kružnici, přidá hranu e do kostry: K := K ∪ {e}.
V každém případě se e odebere z F a cyklus se opakuje pro další hranu.
Zatímco v Kruskalově algoritmu vytváření kostry vypadá nahodile, u Jarníkova
algoritmu se postupně buduje od pevně zvoleného výchozího vrcholu
v. Algoritmus pracuje s množinou již připojených vrcholů A, na začátku je
A := {v}, K := ∅. V každém průchodu algoritmus vybírá minimální hranu
mezi A a V − A a přidává ji do K. Připojený vrchol z V − A se přidá do
A a cyklus se opakuje. Protože se do K přidávají hrany připojující nové vrcholy,
nemůže vzniknout kružnice. Algortimus končí navštívením posledního
vrcholu, tj. A = V .
Borůvkův algoritmus předpokládá injektivní ohodnocení hran. (Při stejném
ohodnocení některých hran bychom mohli upravit zadání přičtením
drobných hodnot.) Pracuje se s relací ekvivalence ρ na množině vrcholů. Na
začátku je ρ := idV , K := ∅. V každém průchodu algoritmu se pro každou
třídu rozkladu vybere minimální hrana spojující ji s jinou třídou. Všechny
takové hrany přidáme do K a přepočítáme ρ jako nejmenší relaci ekvivalence
obsahující K (slévání bublinek). Na konci algoritmu je ρ = V × V a K je
minimální kostra.
6.4 Další grafové problémy
Graf se nazývá rovinný, pokud ho lze reprezentovat v rovině tak, že se žádné
dvě hrany nekříží.
Příklad 11. (1) Síť mnohostěnu je rovinný graf. (Roztáhneme libovolnou
stěnu a síť promítneme dovnitř.)
(2) Úplný graf o pěti vrcholech K5 ani úplný bipartitní graf pro dvě
tříprvkové množiny K3,3 (úloha o třech studních) nejsou rovinné grafy.
22
Dělením grafu nazýváme graf, který vznikne opakovaným vkládáním vrcholů
do hran (stará hrana se nahrazuje dvěma novými a vrcholem).
Věta 18. (Kuratowského) Graf je rovinný právě tehdy, když neobsahuje podgraf
izomorfní dělení grafu K5 nebo K3,3.
Obarvením grafu se nazývá zobrazení c : V → C, kde C je množina
„barev“, splňující {u, v} ∈ E → c(u) = c(v) (sousední vrcholy mají různé
obarvení). Minimální počet barev |C| se nazývá barevnost grafu.
Příklad 12. (1) Úplný graf s n vrcholy Kn má barevnost n.
(2) Každý rovinný graf má barevnost nejvýše 4 (dlouho otevřený problém,
dokázáno užitím počítače).
(Uzavřeným) eulerovským tahem se nazývá uzavřený sled, který prochází
každou hranou právě jednou. Graf se nazývá eulerovský, pokud v něm existuje
eulerovský tah.
Věta 19. Graf je eulerovský právě tehdy, když je souvislý a stupeň každého
vrcholu je sudý.
Důkaz. Pokud je graf souvislý a stupně jsou sudé, musí být každý stupeň
alespoň 2. Graf je konečný, lze tedy sestrojit uzavřený sled, v němž se žádná
hrana neopakuje (tzv. tah). Uvědomme si, že se vrcholy mohou v tahu objevit
opakovaně, ale u každého se vždy využije sudý počet hran. Pokud tah není
maximální, znamená to, že z některého jeho vrcholu vede zatím nepoužitá
hrana. Z této hrany lze opět sestrojit uzavřený tah s jinými hranami, než
má původní tah. (I když dojde k překřížení, sudost stupňů umožňuje odchod
po nepoužité hraně.) Nový tah navážeme na starý (princip přilepování uší).
Postupným opakováním tohoto postupu najdeme maximální tj. eulerovský
tah.
Opačná implikace je jednoduchá. Souvislost je zřejmá, sudost vyplývá
z faktu, že tah do každého vrcholu jednou hranou vstupuje a druhou jej
opouští.
Hamiltonovskou kružnicí se nazývá kružnice procházející všemi vrcholy.
Graf se nazývá hamiltonovský, pokud v něm existuje hamiltonovská kružnice.
23