Cvičení se koná každý čtvrtek v 17:20 na Troji v učebně T10 (záznam v SISu), stránky k přednášce najdete zde.
Pokud budete chtít přijít na konzultaci, napište mi e-mail (janvolec-tady_neco_chybi-jikos.cz) a domluvíme se.
Domácí úlohy budou zadávány na témata, která byla probrána na cvičeních. Na jejich vypracování budou zpravidla dva týdny. Řešení se odevzdávají písemně na začátku příslušného cvičení, kde si společně ukážeme jejich řešení. Pokud na cvičení neplánujete přijít, můžete před jeho začátkem zaslat řešení e-mailem.
Úvodní cvičení, opakovali jsme si pojmy z diskretní matematiky, dirichletův princip, metody pro sčítání různých sum, základní třídy grafů, barevnost grafů (nejen rovinných).
Suploval Pavel Klavík – barevnost degenerovaných grafů, doplněk rovinného grafu s 11 vrcholy není rovinný, kritéria pro existenci Eulerovského tahu (ne nutně uzavřeného), každý graf s min. stupněm d obsahuje kružnici délky alespoň d+1 a cestu délky d, Turánova věta pro max. počet hran v grafu bez trojúhelníků.
Princip inkluze a exkluze, počet uspořádání pohádkových bytostí (bez dvou stejného typu za sebou), počet čísel, která nejsou dělitelná 4, 5 a 6, počet surjektivních zobrazení a vztah s počtem ekvivalencí, Stirlingova čísla pro počet ekvivalencí s daným počtem tříd, doplňky kružnic a rovinnost (doplňky C8, ani C7 rovinné nejsou, naopak doplňek C6 rovinný je).
Suploval Martin Mareš – vytvořující funkce a základní operace s nimi, úlohy na lineární rekurence.
Počet způsobů pro součet čísla n pomocí kladného počtu sčítanců, Catalanova čísla a vztahy mezi cestami v mřížce vs. počtem uzávorkování vs. počtem zakořeněných binárních stromů, vytvořující funkce pro pro n2 a pro její částečné součty.
Suploval Pavel Klavík – další dávka rekurencí a vytvořujících funkcí.
Řešení některých domácích úloh ze serie na vytvořující funkce, vzorec pro n-té čtverečkové číslo, zobecněná binomická věta, konečné projektivní roviny a vztah ke klasické projektivní rovině, zaměnitelnost axiomů P0 (existují 4 body takové, že každá přímka prochází nejvýše dvěma z nich) a P0' (existují 2 přímky, každá s alespoň 3 body) v definici KPR.
Psala se písemka, pak se ukazovala správná řešení úloh z písemky, Fanova rovina není 2-obarvitelná.
Korespondence mezi KPR a NOLČ, Hallova věta pro existenci SRR a pro existenci párování v bip. grafu pokrývající jednu partitu, aplikace Hallovy věty -- rozšiřování lat. obdélníků na latinský čtverec, ekvivalentní podmínky pro existenci perfektního párování v bipartitním grafu, k-regulární bip. graf je 1-faktorizovatelný, bipartitní graf, v němž každý vrchol z partity A má stupeň větší nebo roven stupňům všech vrcholů z partity B, obsahuje perfektní párování, pro dvě (různá) uniformní rozdělení množiny existuje jeden SRR, který reprezentuje obě rozdělení.
Párování v grafu je největší právě když neexisuje volná střídavá cesta, počet perfektních párování v Kn,n a K2n, těžší aplikace Hallovy věty -- každý rovinný graf má orientaci takovou, že výstupní stupeň všech vrcholů je nejvýše tři, každý 2k-regulární graf je 2-faktorizovatelný. Zesílení Hallovy věty na spolky s alespoň m členy, dolní odhad na počet latinských čtverců řádu n.
Toky v hyperkrychli, Königova věta a dualita mezi největší nezávislou množinou a největším párováním v bipartitním grafu, vrcholové pokrytí jako duální pojem k nezávislé množině, König-Oreho formule pro velikost největšího párování, toky v síti, kde je více zdrojů a spotřebičů (navzájem zaměnitelnými), množinová verze Mengerovy věty (disj. cesty mezi dvěma množinami) a souvislost s pojmem spojovanost (linkovost) grafu, ušaté lemma a silně souvislá orientace 2-souvislého grafu, G je 2-souvislý právě když pro každé dva vrcholy existuje kružnice jimi procházející, v 2-souvislém grafu existuje kružnice i pro každou dvojici vrchol, hrana. Pozor, příští týden bude písemka!
Psala se písemka, pak se ukazovala správná řešení úloh z písemky, k-regularní bipartitní graf neobsahuje artikulaci.
Ramseyovo číslo pro trojúhelník, pěticyklus je (jediný) graf na 5 vrcholech bez kliky/nezávislé velikosti 3, každý graf na 6 vrcholech obsahuje dokonce dvě trojice, kde každá je klika/nezávislá, R(m,n) > (m-1) × (n-1), Schurova věta, Erdös-Szekeresova věta z diskrétky o monotónní vybrané podposloupnosti, Erdös-Szekeresova věta o bodech v konvexní poloze.
| 1. úk. | 2. úk. | 3. úk. | 4. úk. | 5. úk. | 6. úk. | Σ př. | akt. | pí. 1 | pí. 2 | Σ | záp. | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 33 | 31 | 28 | 19 | 40 | 36 | 187 | 0 | 54 | 61 | 302 |
Objevíte-li někde chybu, dejte mi, prosím, vědět.
Stránka vytvořena za pomoci programů vi, bash a perl. Poslední změna: 10.06.2010