Cvičení z Kombinatoriky a grafů I.

Zde budou informace pro studenty Kombinatoriky a grafů I. (2012/2013), úterní cvičení od 15:40 k přednáškám O. Pankráce a V. Jelínka.

Co se dělalo na cvičení:

  • 1. hodina: Dolní odhad faktoriálu pomocí indukce, oba odhady Harmonického čísla pomocí integrálu (ln(n)≤H(n)≤ln(n)+1), odhad prostředního kombinačního čísla pomocí odhadu na faktoriál (nejlépe použitím Stirlinga), porovnání větších kombinačních čísel (pascalův trojúhelník).
  • 2. hodina: Zopakování vytvořujících fcí, pár slov o konvergenci, přehled základních vytvořujících fcí a operací s nimi, příklad: 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, určování vytvořujících fcí posloupností: (1,2,1,4,1,8,...), (2,1,4,3,6,5,...), (0,0,0,6,-6,6,...), (1/i!), lemátko.
  • 3. hodina: Použití lemátka na spočítání problému Šatnářky pomocí vytvořujících fcí, Hledání explicitního vzorce z rekurentního pomocí VF: (a_0=0,a_{n+1}=a_n+1);(a_0=1,a_{n+1}=2a_n+3);(a_0=0,a_{n+1}=2a_n+3n);(a_0,a_1,a_{n+2}=(a_n+a_{n+1})/2);pomocí logaritmu - (a_0=2,a_1=8,a_{n+2}=\sqrt{a_n a_{n+1}}). Zopakování rozkladu na parciální zlomky a dělení polynomů.
  • 4. hodina: Jak nepočítat VF (Pozor na obor platnosti při integrování. Musí se shodovat s oborem konvergence, tedy speciálně nějaké okolí nuly.); Zopakování definic KPR(X,P) (podmínky P0,P1,P2); 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 vynechám P0; Důkaz že Fanova rovina (braná jako hypergraf) není 2-obarvitelná; Zopakování definice ortogonálních latinský čtverců OLČ(n); Definice ortogonální tabulky OT(n,S) (viz. 4.úkol); Důkaz věty: Existuje |OLČ(n)|≥S-2 <=> existuje OT(n,S).
  • 5. hodina: Zopakování pojmů z přednášky (K(G)=K(G-e)+K(G:e)), počítání koster konkrétního grafu, Připomenutí základních pojmů z lineární algebry (determinant, operace s determinantem, počítání determinantu), Definice Laplaceovy matice Q, Vyslovení věty co by měla být dokázána v lineární algebře (K(G)=det(Q_{1,1})) a její použití na důkaz K(K_n), cvičení kolik koster má graf: (K_n s podrozdělenou hranou),(K_n slepená za hranu s C_m),(K_{n,m} tedy úplného bipartitního grafu).
  • 6. hodina: Písemka 1
  • 7. hodina: Shrnutí a nastínění řešení písemky, opakování definic: (Síť, tok, velikosti toku, celočíselnost, zbytková síť, vylepšující cesta, st-cesta, řez), pojmy (maxflow-mincut dualita, Ford-Fulkersonův algoritmus), Procvičování pojmů a rozhodování pravdivosti tvrzení o sítích: (např. Celočíselná síť má maximální velikost toku celočíselnou), Hledání max toku na konkrétním příkladě a dokazování maximality, příklad nekonečnosti Ford-Fulkersonova algoritmu a jeho nekonvergence k řešení.
  • 8. hodina: Opakování definic (řez, souvislost, k-souvislost) a vět (Mengerovi věty, K_v(G)≤K_e(G)) z přednášky, Jednoduché příklady (určování vrcholové a hranové souvislosti konkrétních grafů, hledání grafů splňujících požadavky na vrcholovou, hranovou souvislost a minimální stupeň), Ušaté lemma + Důkaz, ušatá dekompozice a podle ní dokázána věta (2-v-souv. graf, který není trojúhelník obsahuje hranu po jejímž zkontrahování zůstane gaf 2-v-souvislý), Dokazování dalších ekvivalentních charakteristik 2-v-souvislých grafů.
  • 9. hodina: Opakování definic a vět z přednášky (Párování, vrcholové pokrytí a jejich vztah, Königova věta), další definice (perfektní párování, 1-faktor, faktorizovatelnost), příklady (hledání počtu perfektních párovní úplného grafu, k-regulární bipartitní graf je 1-faktorizovatelný), Hallova věta z přednášky a její rozšíření na 2-SRR, ověřování Hallovi podmínky na příkladech.
  • 10. hodina: Opakování Ramseyových vět z přednášky (Symetrická a asymetrická verze pro libovolný G, perze pro k barev), naznačení rozdílu mezi N (N z Ramseovy věty) a R=min(N) (Ramseyovo číslo), Různá zobecnění Ramseyových vět (barvení vrcholů, orientované grafy, grafy se smyčkami, více barevných funkcí, podmínky pro hrany a hledání K_3 s dannou konkrétní hranou, verze pro k barev a indukovaný podgraf, hledání monochromatické liché K_3 při očíslovaných vrcholech)
  • 11. hodina: Naznačení příkladu, že ne každý částečně vyplněný latinský čtverec lze doplnit, Opakování vět z přednášky (Schur, nekonečný Ramsey pro p-tice), Zopakování základní Ramseyovy konečné věty, Odhady na Ramseyovo číslo R(k,l) i s důkazy (viz. Kapitoly) (R(k,l)≤R(k-1,l)+R(k,l-1), R(k,l)≤ (k+l-2) nad(k-1), R(k)≤4^(k-1)/(2k-2),R(k)≥2^(k/2)), Základní odhady (R(k,1)=1,R(k,2)=k), odhadli jsme 9≤R(3,4)≤10.
  • 12. hodina: Písemka 2
  • 13. hodina: Opakování písemky, Naznační řešení domácího úkolu ( R(m,n)<R(m-1,n)+R(m,n-1), pokud jsou oba členy sudé), Pár slov o axiomu výběru, Zopakování samoopravných kódů z přednášky ((n,k,d)-Kód, Hammingova vzdálenost, efektivita kódu, Lineární kódy a jejich výhody, Hammingův kód), Konstrukce hammingova pomocí Fannovy roviny.
  • 14. hodina: Zopakování samoopravných kódů z přednášky ((n,k,d)-Kód, Hammingův kód, kódování a dekódování, odhady: Singletonův, Hammingův), Definování perfektních kódů (Hamingův, jednoprvkový, opakovací kód liché délky a celouniverzový kód jsou perfektní), Krátké opakování vytvořujících funkcí.

Domácí úkoly:

Požadavky na zápočet:

V průběhu semestru budou 2 písemky, každá po 50 bodech. Po každém cvičení (kromě posledního) budou domácí úkoly za 8 bodů, které bude potřeba odevzdat 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ň 35/104 bodů z úkolů.

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.

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