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>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í