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>kam.mff.cuni.cz


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
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
tel +420 22191 4294

Profile for TarkenCZE-Maso sDýní