lze indukovat tak, že dokážeme platnost tvrzení pro , a následně pro
zkouška
(a dělí b)
prvočíslo
důkaz sporem
důkaz indukcí
příklad – pro X = {1, 2, 3, 4, 5}
Df: pro relace definujeme inverzní relaci
Df: pro relace a definujeme jejich složení
příklad
Značení:
příklady
skládání funkcí
Df: Funkce je
pro prostou: je funkce z Y' do X
přičemž Y' je množina všech obrazů, tedy všech
Df: relace R na X je
Df: (částečné) Uspořádání na množině X je relace R na X, která je reflexivní, antisymetrická a tranzitivní
Df: relace bezprostředního předchůdce
Df: pro ČUM je :
Dk: zvolíme libovolně
Df: pro ČUM je
Df:
n-prvková množina od 1 do n
binomické koeficienty, binomická věta
n kuliček do k přihrádek
šatnářka
odhady faktoriálu
značení
rozšíření grafů
příklady
izomorfismus grafů
pokud vezmeme n vrcholů, kolik existuje grafů s touto množinou vrcholů?
indukovaný podgraf – vyberu si vrcholy z původního grafu a do nového grafu zdědím všechny hrany mezi nimi
cesta v grafu
odebrání vrcholu – musím odebrat odpovídající hrany
nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)
dva druhy souvislosti
popis grafů pomocí matic
pro souvislý graf definujeme vzdálenost mezi dvěma vrcholy = počet hran v nejkratší cestě mezi dvěma vrcholy
důkaz Eulerovy formule (strom má o jeden vrchol víc než hran)
nejdřív musíme otrhat listy a potom je zpátky přidat – nestačí dokázat, že můžeme přidávat listy k grafu o jednom vrcholu a bude to platit stále
věta o charakterizaci stromů – pro graf G jsou tato tvrzení ekvivalentní
definice křivky
stěny nakreslení
které grafy jsou rovinné
kreslení na sféru
operace pro G rovinný
Kuratowského věta
G je nerovinnýG obsahuje podgraf izomorfní s dělením nebo
Dk: Zvolíme pevně, pak indukcí podle .
je-li G maximální rovinný s aspoň 3 vrcholy, ve všech jeho nakresleních jsou všechny stěny trojúhelníky (říká se jim rovinné triangulace)
počet hran pro triangulace
dk: doplníme do G hrany, až získáme maximální rovinný G'
důsledky
rovinný graf bez trojúhelníků
příklady
barvení stromu
věta: graf má barevnost nejvýše dva neobsahuje lichou kružnici
tedy bipartitní grafy jsou ty, které neobsahují liché kružnice
dk:
graf G je k-degenerovaný lineární uspořádání na t. ž.
dk #1: indukcí podle
dk #2:
příklady barvení z praxe
pravděpodobnostní prostor
diskrétní pravděpodobnostní prostor
příklad: n hodů mincí
pravděpodobnostní závorky
příklad (Bertrandův paradox)
příklad
definice nezávislých jevů
jevy jsou po 2 nezávislé, pokud pro libovolnou dvojici z množiny jevů platí, že se pravděpodobnost průniku rovná součinu pravděpodobností
příklad
příklad
míchání karet
věta o linearitě střední hodnoty
důkaz pomocí roztržení sumy
příklad
náhodná veličina
střední hodnota – vážený průměr X (jako „váhy“ použijeme pravděpodobnosti)
jevy
neorientovaný graf
algoritmus: rozdělíme na náhodně
pokud , znovu
věta: Markovova nerovnost
důkaz
důkaz efektivity algoritmu výše
věta o Dlouhém a Širokém
Erdősovo-Szekeresovo lemma
klasifikace platónských těles pomocí rovinných grafů