Cvičení z Kombinatoriky a grafů I.

Zde budou informace pro studenty Kombinatoriky a grafů I (2013/2014), čtvrteční cvičení od 12:20 k přednáškám O. Pangráce.

Domácí úkoly:

1.úkol odevzdávejte do 12:20 dne 27/2/2013
2.úkol odevzdávejte do 12:20 dne 6/3/2013
3.úkol odevzdávejte do 12:20 dne 13/3/2013
4.úkol odevzdávejte do 12:20 dne 27/3/2013
5.úkol odevzdávejte do 12:20 dne 10/4/2013
6.úkol odevzdávejte do 12:20 dne 17/4/2013
7.úkol odevzdávejte do 12:20 dne 15/5/2013
8.úkol odevzdávejte do 12:20 dne 22/5/2013
9.úkol odevzdávejte do 12:20 dne 30/6/2013

Co se dělalo na cvičení:

1. hodina: Definice asymptotické notace (\(O,o,\Omega,\omega,\Theta,\sim\)), Příklady (Jak upravit definici \(O\) pomocí limes superior, vztah \(\sim\) a \(\theta\)), Zopakování z přednášky (Odhady faktoriálu pomocí integrálu + idea, pomocí indukce + idea, Stirlingova formule bez DK, odhady kombinačního čísla a prostřdního kombinačního čísla), Příklady ( Odhad prostředního kombinačního čísla pomocí stirlinga, Odhad Harmonického čísla pomocí integrálu \(\ln{n}\leq H(n)\leq \ln{n}+1\), Odhad \(\sum_{i=1}^n \frac{1}{\sqrt{i}}\sim 2\sqrt{n}\), Vyjádření \(O(1), o(1), n^{O(1)}\) bez použití Asymptotické notace. )
2. hodina: Zopakování vytvořujících fcí VF (rozebrání definice a základní věty o konvergenci a vztahu s Taylorovým polynomem), přehled základních vytvořujících fcí a operací s nimi, Rozdíl mezi explicitním, rekurentním a jiným zadáním posloupnosti, jaký je životní cyklus VF, příklady: Počet řetězců délky \(n\) začínající úsekem z písmen A a B a končící úsekem z písmen C (operace násobení a parciální zlomky), určování vytvořujících fcí posloupností: \((1,2,1,4,1,8,\ldots)\), \((2,1,4,3,6,5,\ldots)\), \((0,0,0,6,-6,6,\ldots)\), \(a_n=\frac{1}{i!}\), lemátko+DK.
3. hodina: Zobecněná binomická věta, Fibonacciho číla pomocí rekurence a nástin toho jak se dají zjistit pomocí lineární algebry s užitím vlastních vektorů a vlastních čísel matice \(\begin{pmatrix} 1&1\\1&0 \end{pmatrix} \), příklady na rekurence a obecné povídání o lineárních rekurentních rovnicích--získání explicitního vzorce: (\(a_0=0,a_{n+1}=a_n+1\);\(a_0=1,a_{n+1}=2a_n+3n\);pomocí logaritmu -- \(a_0=2,a_1=8,a_{n+2}=\sqrt{a_n a_{n+1}}\), připomenutí základních technik: (rozklad na parciální zlomky a přehled operací s VF, odvození operace \(a(x)^{-1}\)), Catalanova čísla.
4. hodina: 1. písemka.
5. hodina: Zopakování příkladu z DU 3/2 (speciálně použití zobecněné binomické věty) a 4 z 1.písemky. Zopakování definic KPR(X,P) (podmínky P0,P1,P2);zopakování vět(Vlastnosti KPR {všechny přímky stejně bodů+DK apod.}, Dualita, konstrukce z konečného tělesa, pojem hypergrafu, Fanova rovina) cvičení:dokázání ekvivalence definic (P0+P1+P2 <=> Pa+P1+P2 <=> Pb+P1+P3), kde (Pa) říká Existují 2 přímky, každá obsahuje alespoň tři body. A (Pb) říká, že X nelze pokrýt dvěmi přímkami; Co se stane pokud P0 nahradím (Pc--Každá přímka obsahuje alepoň dva body); Zopakování definice ortogonálních latinský čtverců OLČ(n); Věta o maximálním počtu OLČ(n),Věta o vztahu OLČ(n) a KPR. cvičení: konstrukce OLČ(n) ze \(\mathcal(Z_p)\), počet latinských obdélníků řádu \(2\times n\); Definice ortogonální tabulky OT(n,S) (viz. 4.úkol).
6. hodina: Opakování definic OLČ(\(n\)), KPR(\(n\)), připomenutí některých důležitých vět. Příklady:( #Latinských obdélníků o rozměrech \(2\times n \), Magický čtverec viz. 5. úkol, Latinký obdélník lze doplnit na latinský čtverec. Fanova rovina není \(2\)--obarvitelná ) Opakování Hallovi věty, vztah množinového systému a grafu incidence, Příklady:( KPR má SSR, \(k\)--regulární bipartitní graf má perfektní párování, \(k\)--regulární bipartitní graf je \(1\)--faktorizovatelný, \(2\)-SSR právě tehdy když \(2\)--HP, Právě (\(3,3\))--SAT je polynomiální, ) Pěkný sepsaná Birkhoff---von Neumanova věta o Bistochastických maticích, která byla na přednášce.
7. hodina: Definice (perfektní párování[PP], párování, maximální párování [M] vs. maximální párování vzhledem k inkluzi, vrcholové pokrytí[VP], hranové pokrytí[HP], Znění Königovi věty), Příklady ( max M ≤ min VP; max M ≤ min HP; Graf bipartitní a má PP potom max M = min VP; Jak získám maximální P vzhledem k inkluzi; Najít graf a v něm dvě párování \(M_1,M_2\), tak že \(|M_1|>|M_2|\) a \(M_1\) je maximální vzhledem k velikosti; Nalezněte 2-approximační algoritmus pro min VP; Min VP= \(|V|-\max( \alpha(G))\). )
8. hodina: Opakování toků a řezů v síti z přenášky, Shrnutí FF algoritmu na toky, povídání o dualitě, příklady (Nalézt min. řez v konkrétní síti, úprava algoritmu pro kapacity ve vrcholech, DK Königovy věty o bipartitních grafech). Zopakování obecných řezů a \(k\)-souvislosti (vrcholové i hranové varianty), Zopakování Mengerových vět a ušatého lematu, Příklady ( určení souvislosti konkrétních grafů (\(K_n,\ K_n-e,\ K_{m,n}\), artikulace, most a další), v \(2\)-v-souvislém grafu, který není \(K_3\) vždy existuje hrana po jejiíž kontrakci graf zůstane \(2\)-v-souvislý, Rozhodnutí zda platí: V každém \(2\)-v-souvislém grafu \(G\) existuje kružnice \(C\), tž. graf \(G-C\) zůstane \(2\)-v-souvislý. )
9. hodina: jak je to s druhou implikací v domácí úloze s magickým čtvercem, písemka 2.
10. hodina: Opakování 2--souvislosti z minula, hlavně ušaté lemma, co je to artikulace a most, cvičení: ( Leží každé 2 vrcholy (hrany) na společné kružnici. Ušaté lemma pro hranovou souvislost. ), Kostry, připomenutí pojmů z přednášky ( rekurentní vztah \(\mathcal{K}(G)=\mathcal{K}(G:e)+\mathcal{K}(G-e)\) pro všechna \(e\), determinant laplaceovy matice bez řádku a sloupce. ) Základní pozorování (jak se chová most, artikulace, nesouvislý graf, smyčky a multihrany při počítání koster), cvičení ( Počítání koster konkrétních grafů (\(C_n,\ K_n-e\ \), \(K_n\) slepená hranou s \(C_m\) ). )
11. hodina: Státní svátek --- cvičení nebude.
12. hodina: Státní svátek --- cvičení nebude.
13. hodina: Opakovaní z přednášek extremální kombinatorika (maximální počet hran pro grafy bez \(K_3,K_4,K_k,C_4\), náznak turánový věty). Opakování z přednášek (Základní varianta Ramseyovy věty + nekonečná verze + nástin DK indukcí +princip kompaknosti,spodní odhad ramseyova čísla, rozšíření na p-tice či více barev), Příklady (\(R(k,1), R(k,2), R(3,4), R(k,l)≤R(k-1,l)+R(k,l-1)-1\) pokud jsou obě \(R(k-1,l)\) a \(R(k,l-1)\) sudé, varianta Ramseyovy věty pro barvení prvků čtvercové matice při hledání monochromatické podmatice a hledání protipříkladu na tuto větu pokud je podmatice definována symetricky).
14. hodina: Plán Kódy.

Požadavky na zápočet:

V průběhu semestru budou 2 písemky, každá po 50 bodech. Po skoro každém cvičení (10 krát) budou domácí úkoly po 9 bodech jedna série, které bude potřeba odevzdat vždy do dalšího cvičení!

Zápočet lze získat za splnění všech následujících podmínek:

Alespoň 100 bodů celkem.
Alespoň 50/100 bodů z písemek.
Alespoň 30/90 bodů z úkolů.

Docházka povinná tradičně nebude, ale bude možnost získat další body za aktivitu v hodinách, které se nově budou přičítat do poviných bodů z písemek či úkolů dle vaší volby.

Pokud někdo o trochu nesplní požadavky, tak přesto může dostat u mě zápočet za vyřešení většího množství obtížných příkladů a/nebo napsáním těžké písemky popřípadě ústním dozkoušením.

Výsledky a nárok na zápočet:

Dosavadní výsledky v google dokumentu.

masarik<a>mimuw.edu.pl

CENT building room 03.111, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic