Co jsme dělali
23.2.2011 Opakování diskrétní matematiky, zejména počítání všeho možného (relací, funkcí, grafů, stromů) a porovnávání téchto počtů.
2.3. Porovnávání funkcí pomocí O-notace. Počet surjektivních zobrazení z 5-prvkové množiny do 3-prvkvové.
9.3. Počítání všeho možného - zejména úlohy na Princip inkluze a exkluze. Dopočítané výsledky zde (1.4.2011 oprava v úloze 4).
16.3. Simulace hodu dvojicí šestistěnných kostek pomocí jedné čtyřstěnné a jedné devítistěnné s vhodně očíslovanými stěnami. Hledání vytvořující funkce k dané posloupnosti a naopak posloupnosti k funkci.
23.3 Dokončení z minula. Řešení rekurencí.
30.3. 1. písemka. Ještě jedna rekurence (bonusová úloha z písemky).
6.4. Catalanova čísla a objekty, které jsou jimi počítány:
1) Korektní uzávorkování s n páry závorek - např. pro n=3 jich je 5, a to
()()(), ()(()), (())(), (()()), ((())). (pomocí bijekce na binární stromy).
2) Mřížové cesty (1,1)->(n+1,n+1), které nikdy nejdou pod diagonálu. (pomocí
bijekce s korektními uzávorkováními i ověřením rekurzivního vztahu, kterým se
Catalanova čísla definují) Také jsme je spočítali přímo (přes bijekci mezi
cestami (1,1)->(n+1,n+1), které se dostanou pod diagonálu se všemi mřížovými
cestami (1,1)->(n,n+2)).
3) Triangulace (n+2)-úhelníka s očíslovanými vrcholy - spojuji dvojice vrcholů,
abych dostal vnitřek mnohoúhelníka rozkrájený na trojúhelníky a aby se nově
přidané hrany navzájem nekřížily. (ověřením rekurzivního vztahu)
Triangulace pro n=4.
13.4 Fibonacciho čísla: počet posloupností 0 a 1, kde nejsou dvě 0 vedle sebe.
Konečné projektivní roviny: příklady splňující (P1) a
(P2), ale ne (P0); ekvivalentní znění (P0) (alespoň 2 přímky s alespoň 3 body),
nemožnost nakreslení Fanovy roviny přímkami v euklidovské rovině.
20.4. Toky: FF na zadané síti; síť o 4 vrcholech, kde FF algoritmus potřebuje libovolně mnoho iterací a síť
s reálnými kapacitami, kde FF algo. neskončí nikdy (obojí při špatně volených zlepšujících cestách) a zmínka, jak to lze napravit;
kapacity na hranách i na vrcholech, zmínka o minimálních i maximálních kapacitách na hranách.
27.4. Stupeň souvislosti grafu : O kolik nejvíce může
vzrůst/klesnout vrcholová/hranová souvislost při odebrání hrany/vrcholu?
Vrcholová souvislost grafu d-dimenzionální krychle je d.
Pro libovolná k>=1 a l>=k najděte graf, který je vrcholově k-souvislý a hranově l-souvislý.
4.5. Hallova věta: Každý k-regulární bipartitní graf má perfektní párování.
Hrany rovinného grafu lze zorientovat tak, aby z každého vrcholu vycházely nejvýše 3 hrany.
Grafy bez K_{2,2}: Horní odhad na počet hran grafu bez K_{2,t}.
11.5. 2. písemka. (v pdf souboru už jsou opraveny chyby, které byly během písemky nalezeny)
18.5. Ramseyova věta
